Python统计质数个数的算法优化再优化-创新互联

关于判断自然数是否质数的算法，网上列举出几种算法，而且速度越来越快，常见的比较快的算法是：“任何一个自然数，总可以表示成以下六种形式之一：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元起，快前往官网查看详情吧