素数算法python · 质数判断完全攻略

从古老的埃拉托斯特尼筛法到现代密码学依赖的米勒-拉宾概率测试,本指南覆盖网民最关心的〈素数算法python〉实现与周边知识。

⚡ 试除法优化

仅需检查到√n,且跳过偶数。时间复杂度O(√n)。适合小整数判断。

基础必知

🧪 埃氏筛法

批量生成素数列表,时间复杂度O(n log log n)。Python中可用bytearray优化内存。

🔐 米勒-拉宾

概率性测试,对于大整数极高效。RSA密钥生成的核心算法之一。

〔筛法与判断〕 网友们还关心

① 埃拉托斯特尼筛法 (Sieve of Eratosthenes)

这是最经典的素数算法python实现之一。基本思想是从2开始,将每个素数的倍数标记为合数。Python代码简洁优雅:

def sieve(n):
    is_prime = [True] * (n+1)
    is_prime[0]=is_prime[1]=False
    for p in range(2, int(n**0.5)+1):
        if is_prime[p]:
            for multiple in range(p*p, n+1, p):
                is_prime[multiple] = False
    return [i for i, prime in enumerate(is_prime) if prime]

⚙️ 复杂度:O(n log log n)。对于n=10^6,仅需约0.05秒。网民常搜索“python素数筛法优化”即指此。

② 线性筛 (欧拉筛)

线性筛保证每个合数只被其最小质因子筛掉,达到O(n)复杂度。在素数算法python进阶中备受关注。

def linear_sieve(n):
    primes = []
    is_prime = [True]*(n+1)
    for i in range(2, n+1):
        if is_prime[i]:
            primes.append(i)
        for p in primes:
            if i*p > n: break
            is_prime[i*p] = False
            if i % p == 0: break
    return primes

※ 当n=10^7时,线性筛比埃氏筛快约30%,且内存访问更规律。

③ 分段筛 (Segmented Sieve)

用于生成超大区间[L, R]内的素数,解决内存不足问题。网民常问“python大范围素数”时推荐此方法。

def segmented_sieve(L, R):
    limit = int(R**0.5)+1
    base_primes = sieve(limit)
    is_prime = [True]*(R-L+1)
    for p in base_primes:
        start = max(p*p, ((L+p-1)//p)*p)
        for j in range(start, R+1, p):
            is_prime[j-L] = False
    return [i+L for i, prime in enumerate(is_prime) if prime and (i+L)>1]

◤ 典型应用:查找10^12附近的素数区间。

〔概率测试·米勒拉宾〕 深度解析

🔍 米勒-拉宾素性测试

素数算法python中用于大整数的首选。基于费马小定理的强化版本。对于32位整数,只需检测特定基{2,7,61}即可确定素性。

基数集合适用范围确定性
{2,3,5,7,11}< 2,152,302,898,747✅ 确定
{2, 325, 9375, 28178, 450775, 9780504, 1795265022}< 2^64✅ 确定
def miller_rabin(n, k=10):
    if n < 2: return False
    if n in (2,3): return True
    if n%2==0: return False
    r, d = 0, n-1
    while d%2==0:
        r+=1; d//=2
    for _ in range(k):
        a = random.randrange(2, n-1)
        x = pow(a, d, n)
        if x==1 or x==n-1: continue
        for _ in range(r-1):
            x = pow(x,2,n)
            if x==n-1: break
        else: return False
    return True

〔性能优化·时间轴〕

📌 基础试除 (√n优化)

早期素数算法python学习者必写。使用6k±1规则可减少判断次数。

if n % 2 == 0 or n % 3 == 0: return False 然后步长6循环。

📌 缓存小素数

预生成前1000个素数列表,对中小整数快速试除。网民搜索“python素数表”高频词。

📌 NumPy向量化

使用Python科学计算库NumPy进行数组操作,筛法速度提升5~10倍。示例:np.ones(n+1, dtype=bool)。

〔热点问答·网友最关心〕

❓ Python判断素数最快方法?

对于小于10^18,推荐米勒-拉宾确定基版本;批量生成用埃氏筛或线性筛。

❓ 如何用Python生成第10001个素数?

使用筛法估计上界约为n log n + n log log n,然后筛选。第10001个素数是104743。

❓ 素数在密码学中的作用?

RSA加密依赖大素数乘积难以分解。素数算法python常用于生成512位以上安全素数。

〈 周边知识·素数分布 〉

素数定理指出π(n) ~ n / ln(n)。网民常搜索“python素数个数统计”。以下为示例数据:

nπ(n)n/ln(n)近似
10^3168144.7
10^67849872382
10^95084753448254942

◢ 梅森素数搜索常与Python分布式计算结合,如GIMPS项目使用Lucas-Lehmer测试。

📋 快速参考:常用素数算法python复杂度

※ 以上所有代码均可在Python 3.10+环境直接运行。