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技术站