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

1、使用质数定义计算

1. #version1import datetime    #导入模块计算效率start = datetime.datetime.now()
2. count = 0
3. for x in range(2,100000):     #求指定范围内的质数
4.     for i in range(2,x):      #除以1和本身之外的数
5.         if x % i == 0:
6.             break
7.     else:
8.         #print(x)
9.         count += 1
10. delta = (datetime.datetime.now() - start).total_seconds()    #total_seconds()总秒数
11. print('count=',count,'delta=',delta)    #墙上的时间
13. #执行结果：
14. count= 9592 delta= 148.146291    #效率极差

复制代码

2、优化1：经计算，临界值为开方值

1. #version2:优化
3. import datetime    #导入模块计算效率
4. start = datetime.datetime.now()
5. count = 0
6. for x in range(2,100000):
7.     for i in range(2,int(x ** 0.5 + 1)):   #优化1，经测试:临界值为开方值
8.         if x % i == 0:
9.             break
10.     else:
11.         #print(x)
12.         count += 1
13. delta = (datetime.datetime.now() - start).total_seconds()    #total_seconds()总秒数
14. print('count=',count,'delta=',delta)
16. #执行结果：
17. count= 9592 delta= 1.084154    #效率极大提高

复制代码

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

1. #version3:优化+
3. import datetime    #导入模块计算效率
4. start = datetime.datetime.now()
5. count = 1
6. #print(2)    #从3开始，自己打印2
7. for x in range(3,100000,2):                   #优化2:从3开始的奇数
8.     #for i in range(3,int(x ** 0.5 + 1)):     #优化3:奇数不用和2取模
9.     for i in range(3, int(x ** 0.5) + 1,2):   #优化4:即也不用和偶数取模
10.         if x % i == 0:
11.             break
12.     else:
13.         #print(x)
14.         count += 1
15. delta = (datetime.datetime.now() - start).total_seconds()    #total_seconds()总秒数
16. print('count=',count,'delta=',delta)    #墙上的时间
18. #执行结果：
19. count= 9592 delta= 0.553471    #性能进一步提高

复制代码

4、优化3：5的倍数全是合数，剔除5的倍数

1. #version4:优化++
3. import datetime    #导入模块计算效率
4. start = datetime.datetime.now()
5. count = 1
6. #print(2)    #从3开始，自己打印2
7. for x in range(3,100000,2):                   #优化2:从3开始的奇数
8.     if x > 10 and x % 5 == 0:
9.         continue                              #优化5:剔除5的倍数
10.     #for i in range(3,int(x ** 0.5 + 1)):     #优化3:奇数不用和2取模
11.     for i in range(3, int(x ** 0.5) + 1,2):   #优化4:即也不用和偶数取模
12.         if x % i == 0:
13.             break
14.     else:
15.         #print(x)
16.         count += 1
17. delta = (datetime.datetime.now() - start).total_seconds()    #total_seconds()总秒数
18. print('count=',count,'delta=',delta)    #墙上的时间
20. #执行结果：
21. count= 9592 delta= 0.493866

复制代码

5、思考，总结，再优化：

质数：所有的质数除过2，都是奇数；
质数：临界值（开方值）；
质数：质数*质数肯定不是质数，给定列表存放已知质数，使用该列表值进行判断，在该值的基础上锁定临界值；
孪生质数：大于3的质数只有6N-1和6N+1两种形式，如果6N-1和6N+1都是素数，成为孪生素数（效率也挺高）

1. import datetime
2. n = 100000
3. count = 2
4. primenumber = [3]
5. start = datetime.datetime.now()
6. for i in range(5,n + 1,2):
7.     flag = False
8.     x = int(i ** 0.5)
9.     for j in primenumber:
10.         if j > x:
11.             flag = True
12.             break
13.         if i % j == 0:
14.             flag = False
15.             break
16.     if flag:
17.         count += 1
18.         #print(i)
19.         primenumber.append(i)
20. end = (datetime.datetime.now() - start).total_seconds()
21. print("count=",count,'  ',"time=",end)
23. #执行结果：
24. count= 9592    time= 0.449377

复制代码

1. import datetime
2. n = 100000
3. count = 3
4. primenumbers = [3,5]
5. start = datetime.datetime.now()
6. x = 7
7. step = 4
8. while x < n:
9.     flag = False
10.     j = int(x ** 0.5)
11.     if x % 5 != 0:
12.         for i in primenumbers:
13.             if i > j:
14.                 flag = True
15.                 break
16.             if x % i == 0:
17.                 flag = False
18.                 break
19.         if flag:
20.             count += 1
21.             primenumbers.append(x)
22.     x += step
23.     step = 4 if step == 2 else 2
25. end = (datetime.datetime.now() - start).total_seconds()
26. print("count=",count,'  ',"time=",end)
28. #执行结果：
29. count= 9592    time= 0.380034

复制代码

6、质数的应用：

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