VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > temp > python入门教程 >
  • 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、质数的应用:

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

 
出处:https://www.cnblogs.com/djdjdj123/p/16925678.html

相关教程