基于Python的高效埃拉托斯特尼筛法实现技术问询

给你分享一个用Numpy实现的埃拉托斯特尼筛法，专门用来生成前N个自然数中的素数。它完美兼顾了代码简洁性、CPU执行效率，还尽可能减少了循环和条件判断的使用：

核心实现代码 #

import numpy as np
N = 10**5
a = np.array(range(3,N,2))
for j in range(0, int(round(np.sqrt(N),0))):
    a[(a!=a[j]) & (a%a[j] == 0)] = 0
a = a[a!=0]
a = [2]+list(a)

简单思路拆解 #

• 第一步就跳过所有偶数，直接生成3到N的奇数数组，一下子减少了一半的数据处理量
• 借助Numpy的向量化操作替代传统嵌套循环，充分利用CPU的并行计算能力，效率提升明显
• 只遍历到√N的位置，这是筛法的经典数学优化，避免不必要的计算
• 最后把唯一的偶素数2补到结果列表开头，得到完整的素数集合

在Intel Core I5处理器上，这段代码可以快速生成前10^5个自然数中的所有素数。

内容的提问来源于stack exchange，提问作者Rob