关于判断自然数是否质数的算法，网上列举出几种算法，而且速度越来越快，常见的比较快的算法是：“任何一个自然数，总可以表示成以下六种形式之一：6n，6n+1，6n+2，6n+3，6n+4，6n+5（n=0,1,2...）我们可以发现，除了2和3，只有形如6n+1和6n+5的数有可能是质数。且形如6n+1和6n+5的数如果不是质数，它们的因数也会含有形如6n+1或者6n+5的数”，因此用Python可以得到如下算法代码：
为磐安等地区用户提供了全套网页设计制作服务，及磐安网站建设行业解决方案。主营业务为
成都网站建设、成都网站制作、磐安网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！
# 统计一亿以内的质数
import time
from numba import jit
# 方法1
# 引入numba库的jit装饰器进行加速运算
@jit
def test1(end):
count = 0
start = 0
def step_two(x):
for i in range(5, int(x ** 0.5) + 1, 6):
if (x % i == 0) or (x % (i + 2) == 0):
return False
return True
if end >3:
count = 2
start = 4
for x in range(start,end):
if (x % 6 != 1) and (x % 6 != 5):
continue
else:
if step_two(x):
count +=1
return count
if __name__ == '__main__':
end:int = 100000000
now = time.time()
count = test1(end)
print(f'方法1：\n{end:,}以内的质数有{count}个\n耗时：{time.time()-now:.3f}秒。')
为加快运算，该代码已引入numba库的jit装饰器，统计一亿内的质数个数，在我的台式机上运行耗时84秒。
我在外网找到更优化的算法，被称为Sieve算法，先创建一个长度为n、只有True值的长列表，然后把所有公倍数的元素值设为False并排除，最后剩下得到的True元素皆为质数。
参考来源：
Analysis of Different Methods to find Prime Number in Python
# 统计一亿以内的质数
import time
from numba import jit
# 引入numba库的jit装饰器进行加速运算
@jit
def SieveOfEratosthenes(n):
prime = [True for i in range(n+1)]
p = 2
pp = p * p
while(pp<= n):
if (prime[p] == True):
for i in range(pp, n + 1, p):
prime[i] = False
p += 1
pp = p * p
count = 0
for p in range(2, n):
if prime[p]:
count += 1
return count
if __name__ == '__main__':
end:int = 100000000
# 方法2
now = time.time()
count = SieveOfEratosthenes(end)
print(f'方法2：\n{end:,}以内的质数有{count}个\n耗时：{time.time()-now:.3f}秒。')
在jit装饰器的加速作用下，Sieve算法快得惊人，统计一亿内的质数个数仅需2.4秒！
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
本文标题：Python统计质数个数的算法优化再优化-创新互联
路径分享：
http://cdkjz.cn/article/cojooj.html
