python计算质数的几种方法

因为要学着写渗透工具，这几天都在上python编程基础课，听得我打瞌睡，毕竟以前学过嘛。
最后sherry老师留了作业，其中一道题是这样的：

题目：编写python程序找出10-30之间的质数。

太简单了，我直接给出答案：

Prime = [11, 13, 17, 19, 23, 29]
print(Prime)

输出结果：

[11, 13, 17, 19, 23, 29]

当然，这样做肯定会在下节课被sherry老师公开处刑的，所以说还是要根据上课时学的知识写个算法。

1.穷举法

回想一下上课时学了变量、列表、循环语句之类的东西，sherry老师还亲自演示了多重死循环是怎么搞出来的（老师是手滑了还是业务不熟练啊），所以我们还是要仔细思考一下不要重蹈覆辙。

思路：首先要构造一个循环，遍历所有符合条件的自然数，然后一个一个验证是否为质数，最后把符合条件的质数列出来。

# 最开始编的穷举法，简单粗暴，就是性能拉跨。
# P=因数，N=自然数
import time


t0 = time.time()  # 开始时间

Min = 10  # 范围最小值

Max = 30  # 范围最大值

Result = []  # 结果

for N in range(Min, Max):  # 给自然数来个遍历
for P in range(2, N):
if (N % P == 0):  # 判断是否有因数
break  # 有因数那就不是质数，跳出循环
else:

        Result.append(N)

print('计算', Min, '到', Max, '之间的质数')
print(Min, '到', Max, '之间的质数序列:', Result)
print(Min, '到', Max, '之间的质数个数:', len(Result))
print('计算耗时:', time.time() - t0, '秒')

执行结果（计算耗时是最后加上去的）：

到这里作业就搞定了。然后把其他几道题也做完了，发现很无聊，就又切回来想搞点事。这么点计算量，0秒真的有点少，不如趁这个机会烤一烤笔记本的性能，所以直接在Min和Max的值后面加几个0。试试100000-200000。

很尴尬，直接卡住了，这代码有点拉跨啊，完全不符合我的风格。
倒了杯咖啡，终于跑完了。

这个也太夸张，一定是哪里出了问题，很久以前用C写的代码我记得也没那么慢啊。反正周末挺闲的，不如仔细研究一下。

2.函数（CV）大法

为了拓宽一下思路，我决定借鉴一下大佬的代码。听说函数是个好东西，所以就CV了两个函数。

一个函数判断质数，另一个求范围内的所有质数，把它们拼一起，是这个样子：

# 网上学来的，自定义两个函数，但是数值稍微大点就卡死了。
import time


t0 = time.time()

Min = 100000  # 范围最小值

Max = 200000  # 范围最大值


def is_prime(n): return 0 not in [n % i for i in range(2, n//2+1)]  # 判断是否为质数


def gen_prime(a, b): return [n for n in range(

    a, b+1) if 0 not in [n % i for i in range(2, n//2+1)]]  # 输出范围内的质数


print('计算', Min, '到', Max, '之间的质数')
print(Min, '到', Max, '之间的质数序列:', gen_prime(Min, Max))
print('计算耗时:', time.time() - t0, '秒')

稍微改动了一下，还是100000-200000，我们试试看。

嗯，一运行风扇就开始啸叫，CPU都快烤炸了。看来CV大法也不行啊。
经过漫长的烤机，这次结果比上次还惨，300多秒，这两个函数本质上还是穷举法，看来这条路也走不通。

3.穷举法改

我们可以分析一下穷举法的代码，看看有没有什么改进的方法。
首先，通过九年义务教育掌握的数学知识，我们知道，质数中只有2是偶数，所以计算中可以把偶数忽略掉，只计算奇数，工作量立马减半！
其次，在用因数P判断N是否为质数时，如果P足够大的话，比如说PxP>=N的时候，那么后面的循环其实是重复无意义的。因为假设PxQ>=N，那么P和Q必然有一个小于sqrt(N)，只需要计算P<=sqrt(N)的情况就行了。

因为2作为唯一一个偶数，夹在循环里面处理起来很麻烦，所以放在开头处理掉。最终的代码如下：

# 优化后的代码，减少了一些无意义的循环，比以前快多了。
import time


t0 = time.time()

Min = 100000  # 范围最小值

Max = 200000  # 范围最大值

Prime = [2, 3]  # 质数列表

Result = []  # 结果

Loop = 0  # 计算循环次数

if Min <= 2:

    Result.append(2)
if Min <= 3:

    Result.append(3)  # 先把2这个麻烦的偶数处理掉
for N in range(5, Max, 2):
for P in range(3, int(N**0.5)+2, 2):  # 只计算到根号N

        Loop += 1
if (N % P == 0):
break
else:

        Prime.append(N)
if N > Min:

            Result.append(N)

print('计算', Min, '到', Max, '之间的质数')
print(Min, '到', Max, '之间的质数序列:', Result)
print(Min, '到', Max, '之间的质数个数:', len(Result))
print('循环次数:', Loop)
print('计算耗时:', time.time() - t0, '秒')

代码量虽然多了，但是效果还是很明显，100000-200000才0.4秒，快了不知道多少，看来我们的思路是对的。
我决定再加到1000000-5000000，看看能不能撑住。因为输出太多了控制台会卡死，所以改一下，只输出最后一个质数。

总共花了64秒，看来还是有点费劲。

4.穷举法魔改

我们再来分析一下，如果我们用于判断的因数，不是用奇数列表，而是用生成的Prime列表里面的质数，因为质数的个数远远少于奇数，所以第二个循环会少一些工作量呢？可以试试看。但是因为这个改动，需要加一些判断语句进去，所以节省的时间比较有限。

# 别看这个代码比较长，但是跑到1000万也不会卡死，而且还很快。
import time


t0 = time.time()

Min = 1000000  # 范围最小值

Max = 5000000  # 范围最大值

Prime = [2, 3]  # 质数列表

Result = []  # 结果

Loop = 0  # 计算循环次数

if Min <= 2:

    Result.append(2)
if Min <= 3:

    Result.append(3)
for N in range(5, Max, 2):

    M = int(N**0.5)  # 上限为根号N
for P in range(len(Prime)):  # 在质数列表Prime中遍历

        Loop += 1

        L = Prime[P+1]
if (N % L == 0):
break
elif L >= M:  # 上限大于根号N，判断为质数并跳出循环

            Prime.append(N)
if N > Min:

                Result.append(N)
break

print('计算', Min, '到', Max, '之间的质数')
print('最后一个质数:', Result[-1])
print(Min, '到', Max, '之间的质数个数:', len(Result))
print('循环次数:', Loop)
print('计算耗时:', time.time() - t0, '秒')

还是1000000-5000000再试试看

这次耗时22秒，时间又缩短了一大半，但是好像已经没多少改进的空间了，感觉穷举法已经到头了，需要新的思路。

5.埃氏筛法

其实初中数学我们就学过埃氏筛法：
如果P是质数，那么大于P的N的倍数一定不是质数。把所有的合数排除掉，那么剩下的就都是质数了。
我们可以生成一个列表用来储存数字是否是质数，初始阶段都是质数，每次得出一个质数就将它的倍数全部标记为合数。

# 速度已经起飞了。
import time


t0 = time.time()

Min = 1000000  # 范围最小值

Max = 2000000  # 范围最大值

Loop = 0  # 计算循环次数

Result = []  # 结果


Natural = [True for P in range(Max)]  # 自然数列表标记为True
for P in range(2, Max):
if Natural[P]:  # 标记如果为True，就是质数
if P >= Min:

            Result.append(P)  # 添加范围之内的质数
for N in range(P*2, Max, P):   # 将质数的倍数的标记改为False

            Loop += 1

            Natural[N] = False

print('计算', Min, '到', Max, '之间的质数')
print('最后一个质数:', Result[-1])
print(Min, '到', Max, '之间的质数个数:', len(Result))
print('循环次数:', Loop)
print('计算耗时:', time.time() - t0, '秒')

1.6秒，比最高级的穷举法还要快上10多倍，这是数学的胜利。
再试试1-50000000。

很不错，只需要20秒。因为筛法的特性，忽略内存的影响，数值越大，后面的速度反而越快了。

6.欧拉筛法

我们可以仔细分析一下，上面的埃氏筛法在最后标记的时候，还是多算了一些东西，N会重复标记False，比如77，既是7的倍数又是11的倍数，这样会被标记两次，后面的大合数会重复标记多次，浪费了算力，所以标记的时候要排除合数。另外就是P*N大于Max时，后面的计算已经无意义了，也要跳出来。把这些重复的动作排除掉，就是欧拉筛法，也叫线性筛。

# 最终版，优化了很多细节。
import time


t0 = time.time()

Min = 1  # 范围最小值

Max = 50000000  # 范围最大值

Loop = 0  # 计算循环次数

Prime = [2]

Result = []  # 结果

if Min <= 2:

    Result.append(2)

Limit = int(Max/3)+1

Natural = [True for P in range(Max+1)]  # 自然数列表标记为True
for P in range(3, Max+1, 2):
if Natural[P]:  # 标记如果为True，就是质数

        Prime.append(P)
if P >= Min:

            Result.append(P)
if P > Limit:  # 超过Limit不需要再筛了，直接continue
continue
for N in Prime:   # 将质数的倍数的标记改为False

        Loop += 1
if P*N > Max:  # 超过Max就无意义了，直接break
break

        Natural[P * N] = False
if P % N == 0:  # 判断是否为合数
break

print('计算', Min, '到', Max, '之间的质数')
print('最后一个质数:', Result[-1])
print(Min, '到', Max, '之间的质数个数:', len(Result))
print('循环次数:', Loop)
print('计算耗时:', time.time() - t0, '秒')

（因为之前的版本缩进错了，所以更新了这段代码）

同样的条件下耗时11.46秒。这是因为多了一个列表和几行判断语句，加上python的解释型特性，所以实际上并不会快好几倍，但是总体效率还是有50%左右的提升。

好了，这次把老师课堂上讲的变量、列表、循环语句什么的都用上了，算是现买现卖、活学活用吧。我觉得这次的作业怎么说也能拿满分吧，sherry老师记得下次上课夸夸我。