python练习题:求10万以内的质数

1、使用质数定义计算

#version1import datetime    #导入模块计算效率start = datetime.datetime.now()
count = 0
for x in range(2,100000):     #求指定范围内的质数
    for i in range(2,x):      #除以1和本身之外的数
        if x % i == 0:
            break
    else:
        #print(x)
        count += 1
delta = (datetime.datetime.now() - start).total_seconds()    #total_seconds()总秒数
print('count=',count,'delta=',delta)    #墙上的时间

#执行结果:
count= 9592 delta= 148.146291    #效率极差

2、优化1:经计算,临界值为开方值

#version2:优化

import datetime    #导入模块计算效率
start = datetime.datetime.now()
count = 0
for x in range(2,100000):
    for i in range(2,int(x ** 0.5 + 1)):   #优化1,经测试:临界值为开方值
        if x % i == 0:
            break
    else:
        #print(x)
        count += 1
delta = (datetime.datetime.now() - start).total_seconds()    #total_seconds()总秒数
print('count=',count,'delta=',delta)

#执行结果:
count= 9592 delta= 1.084154    #效率极大提高

3、优化2:大于2的偶数全是合数

#version3:优化+

import datetime    #导入模块计算效率
start = datetime.datetime.now()
count = 1
#print(2)    #从3开始,自己打印2
for x in range(3,100000,2):                   #优化2:从3开始的奇数
    #for i in range(3,int(x ** 0.5 + 1)):     #优化3:奇数不用和2取模
    for i in range(3, int(x ** 0.5) + 1,2):   #优化4:即也不用和偶数取模
        if x % i == 0:
            break
    else:
        #print(x)
        count += 1
delta = (datetime.datetime.now() - start).total_seconds()    #total_seconds()总秒数
print('count=',count,'delta=',delta)    #墙上的时间

#执行结果:
count= 9592 delta= 0.553471    #性能进一步提高

4、优化3:5的倍数全是合数,剔除5的倍数

#version4:优化++

import datetime    #导入模块计算效率
start = datetime.datetime.now()
count = 1
#print(2)    #从3开始,自己打印2
for x in range(3,100000,2):                   #优化2:从3开始的奇数
    if x > 10 and x % 5 == 0:
        continue                              #优化5:剔除5的倍数
    #for i in range(3,int(x ** 0.5 + 1)):     #优化3:奇数不用和2取模
    for i in range(3, int(x ** 0.5) + 1,2):   #优化4:即也不用和偶数取模
        if x % i == 0:
            break
    else:
        #print(x)
        count += 1
delta = (datetime.datetime.now() - start).total_seconds()    #total_seconds()总秒数
print('count=',count,'delta=',delta)    #墙上的时间

#执行结果:
count= 9592 delta= 0.493866

5、思考,总结,再优化:

质数:所有的质数除过2,都是奇数;

质数:临界值(开方值);

质数:质数*质数肯定不是质数,给定列表存放已知质数,使用该列表值进行判断,在该值的基础上锁定临界值;

孪生质数:大于3的质数只有6N-1和6N+1两种形式,如果6N-1和6N+1都是素数,成为孪生素数(效率也挺高)

import datetime
n = 100000
count = 2
primenumber = [3]
start = datetime.datetime.now()
for i in range(5,n + 1,2):
    flag = False
    x = int(i ** 0.5)
    for j in primenumber:
        if j > x:
            flag = True
            break
        if i % j == 0:
            flag = False
            break
    if flag:
        count += 1
        #print(i)
        primenumber.append(i)
end = (datetime.datetime.now() - start).total_seconds()
print("count=",count,'  ',"time=",end)

#执行结果:
count= 9592    time= 0.449377
import datetime
n = 100000
count = 3
primenumbers = [3,5]
start = datetime.datetime.now()
x = 7
step = 4
while x < n:
    flag = False
    j = int(x ** 0.5)
    if x % 5 != 0:
        for i in primenumbers:
            if i > j:
                flag = True
                break
            if x % i == 0:
                flag = False
                break
        if flag:
            count += 1
            primenumbers.append(x)
    x += step
    step = 4 if step == 2 else 2

end = (datetime.datetime.now() - start).total_seconds()
print("count=",count,'  ',"time=",end)

#执行结果:
count= 9592    time= 0.380034

6、质数的应用:

应用在密码学领域,都要使用大素数

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:python练习题:求10万以内的质数 - Python技术站

(0)
上一篇 2023年4月2日
下一篇 2023年4月2日

相关文章

  • Python生成随机数的一个标准库-random

    1.介绍 Random库Python中用于生成随机数的一个标准库。计算机没有办法产生真正的随机数,但它可以产生伪随机数。 伪随机数是计算机按照一定的运算规则产生的一些数据,只不过这些数据表现为随机数的形式。计算机中采用梅森旋转算法生成为随机序列,序列中的每一个元素就是伪随机数,由于计算机不能产生真正的随机数,所以伪随机数也就被称为随机数。 Random库包含…

    python 2023年4月27日
    00
  • Python:numpy模块最详细的教程

    一、numpy简介 numpy官方文档:https://docs.scipy.org/doc/numpy/reference/?v=20190307135750 numpy是Python的一种开源的数值计算扩展库。这种库可用来存储和处理大型numpy数组,比Python自身的嵌套列表结构要高效的多(该结构也可以用来表示numpy数组)。 numpy库有两个作…

    Python开发 2023年3月31日
    00
  • Python学习:dict和set类型的用法

    1.什么是dict 我们已经知道,list 和 tuple 可以用来表示顺序集合,例如,班里同学的名字: [‘Adam’, ‘Lisa’, ‘Bart’] 或者考试的成绩列表: [95, 85, 59] 但是,要根据名字找到对应的成绩,用两个 list 表示就不方便。 如果把名字和分数关联起来,组成类似的查找表: ‘Adam’ ==> 95 ‘Lisa…

    Python开发 2023年4月2日
    00
  • python学习:重用父类功能的两种方式

    在子类派生的新方法中如何重用父类的功能方式一:指名道姓调用某一个类下的函数=》不依赖于继承关系 class OldboyPeople: def __init__(self,name,age,sex): self.name=name self.age=age self.sex=sex def f1(self): print(‘%s say hello’ %se…

    Python开发 2023年4月2日
    00
  • Python教程:读取文件有三种方法:(read、readline、readlines)详细用法

    python3中,读取文件有三种方法:read()、readline()、readlines()。 此三种方法,均支持接收一个变量,用于限制每次读取的数据量,但是,通常不会使用。 本文的目的:分析、总结上述三种读取方式的使用方法及特点。 一、read方法 特点:读取整个文件,将文件内容放到一个字符串变量中。 缺点:如果文件非常大,尤其是大于内存时,无法使用r…

    Python开发 2023年4月2日
    00
  • Python教程:IO

    在磁盘上读写文件的功能都是由操作系统提供的,现代操作系统不允许普通的程序直接操作磁盘,所以,读写文件就是请求操作系统打开一个文件对象(通常称为文件描述符),然后,通过操作系统提供的接口从这个文件对象中读取数据(读文件),或者把数据写入这个文件对象(写文件)。 1.读文件 要以读文件的模式打开一个文件对象,使用Python内置的open()函数,传入文件名和标…

    Python开发 2023年3月31日
    00
  • 关于Python封装函数的几道练习题

    1.封装函数,可以判断一个数字是否为偶数 def func(n): if n%2==0: print(“%d是偶数”%n) else: print(“%d是奇数”%n) func(11) # 11是奇数 2.封装函数,可以实现1-n之间所有偶数的打印 def func(n): for i in range(1,n+1): if i%2==0: print(i…

    Python开发 2023年4月2日
    00
  • Python中12个常用模块的使用教程

    1. time模块 import time *一*#时间戳–》结构化时间–》格式化的字符串时间 —————————————————————————– res1=time.localtime(654126574) print(res1 ) #res1===…

    Python开发 2023年4月2日
    00
合作推广
合作推广
分享本页
返回顶部