1、基本算法：
根据素数定义：一个大于1的自然数只能被1和它本身整除，即可利用for循环逐次计算，求解素数，代码如下：
1 n = int(input(‘>>>‘)) 2 3 import datetime 4 start = datetime.datetime.now() 5 6 for i in range(2,n+1): 7 for j in range(2,i): 8 if i % j == 0: 9 break 10 else: 11 print(i,end=‘ ‘) 12 13 delta = (datetime.datetime.now() - start).total_seconds() 14 print() 15 print(delta) 16 ********************************************** 17 D:\untitled\project2\venv\Scripts\python.exe D:/untitled/project2/day1/sushu.py 18 >>>10000 19 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97…… 20 1.062382 21 22 Process finished with exit code 0
2、利用奇偶性优化算法：
根据偶数均可整除2性质，由此可知偶数均不是质数，故可优先排除偶数，现将代码优化如下：
1 n = int(input(‘>>>‘)) 2 print(2,end=‘ ‘) 3 4 import datetime 5 start = datetime.datetime.now() 6 7 for i in range(3,n+1,2): 8 for j in range(3,i,2): 9 if i % j == 0: 10 break 11 else: 12 print(i,end=‘ ‘) 13 14 delta = (datetime.datetime.now() - start).total_seconds() 15 print() 16 print(delta) 17 ************************************************** 18 D:\untitled\project2\venv\Scripts\python.exe D:/untitled/project2/day1/sushu.py 19 >>>10000 20 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83…… 21 0.53969 22 23 Process finished with exit code 0
3、利用所有大于10的质数中，个位数只有1、3、7、9
根据所有大于10的所有奇数，但凡个位数为5的数字均可整除，故可利用此性质再次优化代码：
1 n = int(input(‘>>>‘)) 2 print(2,end=‘ ‘) 3 4 import datetime 5 start = datetime.datetime.now() 6 7 for i in range(3,n+1,2): 8 if i > 10 and i % 10 == 5: 9 continue 10 for j in range(3,i,2): 11 if i % j == 0: 12 break 13 else: 14 print(i,end=‘ ‘) 15 16 delta = (datetime.datetime.now() - start).total_seconds() 17 print() 18 print(delta) 19 ************************************************** 20 D:\untitled\project2\venv\Scripts\python.exe D:/untitled/project2/day1/sushu.py 21 >>>10000 22 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97…… 23 0.501726 24 25 Process finished with exit code 0
4、利用质数平方根性质
假设整数m有一个比它的平方根m^(1/2)还要大的因数的话，即m=k1*k2,其中，k1>=m^(1/2)+1,则其另一个因数k2<=m^(1/2)。因此，整数m的因数（如果有的话）只需循环至m的平方根即可，现将代码优化如下：
1 n = int(input(‘>>>‘)) 2 print(2,end=‘ ‘) 3 4 import datetime 5 start = datetime.datetime.now() 6 7 for i in range(3,n+1,2): 8 if i > 10 and i % 10 == 5: 9 continue 10 for j in range(3,int(i**0.5)+1,2): 11 if i % j == 0: 12 break 13 else: 14 print(i,end=‘ ‘) 15 16 delta = (datetime.datetime.now() - start).total_seconds() 17 print() 18 print(delta) 19 ********************************************************* 20 D:\untitled\project2\venv\Scripts\python.exe D:/untitled/project2/day1/sushu.py 21 >>>10000 22 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97…… 23 0.02498 24 25 Process finished with exit code 0
5、利用大于等于5的质数一定和6的倍数相邻性质
根据所有大于等于5的质数一定和6的倍数相邻性质，对整体代码进行调整：
1 # coding=gbk 2 n = int(input(‘>>>‘)) 3 print(2,3,end=‘ ‘) 4 5 import datetime 6 start = datetime.datetime.now() 7 8 for i in range(5,n,2): 9 if (i+1) % 6 == 0 or (i-1) % 6 == 0:#可能是素数 10 for j in range(5,int(i**0.5)+1,2): 11 if i % j == 0: 12 break 13 else: 14 print(i,end=‘ ‘) 15 16 delta = (datetime.datetime.now() - start).total_seconds() 17 print() 18 print(delta) 19 ********************************************************** 20 E:\python文件夹\venv\Scripts\python.exe E:/python文件夹/sushu.py 21 >>>10000 22 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97…… 23 0.011966 24 25 Process finished with exit code 0
第五种方法要注意大于5的质数一定和6的倍数相邻，但是与6的倍数相邻的不一定是质数。比如i等于223的时候，223-1=222，222除以6得到整数37(代码第9行)，因此223进入循环(代码第10行)，223开方+1等于15，j分别取5、7、9、11、13，223分别除j没有整除，因此输出223是质数(代码13~14行)。比如i等于49，49-1=48，48除以6得到整数8(代码第9行)，因此49进入循环(代码第10行)，49开方+1等于8，j分别取5、7，49除j=7的时候是整除，判断语句生效(代码第11行)，跳出该循环(这里的循环指的是代码第10行的循环，第8行的代码循环进入i=51的新一轮)。
这里一定要注意各层的嵌套问题，不能搞混。
看一看各个方法的运行时间，是逐步降低的，代码的效率是逐步提升的。
原文：https://www.cnblogs.com/linfengs/p/11655837.html