给出一个最快的求素数的算法

12 2025-09-01 10:22

要找到“最快”的求素数算法，我们得先明确几个关键点：

范围：是求某个区间内的所有素数，还是判断单个超大数是否为素数？
时间复杂度：是理论最优，还是实际最快？
实现复杂度：是否允许使用复杂的数学理论或高性能计算资源？

✅ 最快求区间素数的算法：分段筛（Segmented Sieve）

如果你是要生成一个大区间内的所有素数（比如 1 到 10^12），那么：

分段筛（Segmented Sieve） 是实际中最快、内存可控的算法。

✅ 原理：

先用普通筛法（如埃氏筛）预处理出 [2, √n] 内的所有素数。
将目标区间 [L, R] 分成若干段，每段长度约为 √R。
对每一段，用预处理的素数去标记非素数。
剩下的就是素数。

✅ 时间复杂度：

预处理：O(√R log log √R)
每段筛：O((R - L + 1) log log R)
总体接近线性，且内存可控。

✅ 示例代码（Python）：

Python

复制

import math

def simple_sieve(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0:2] = [False, False]
    for i in range(2, int(math.isqrt(limit)) + 1):
        if is_prime[i]:
            for j in range(i*i, limit+1, i):
                is_prime[j] = False
    return [i for i, val in enumerate(is_prime) if val]

def segmented_sieve(L, R):
    limit = int(math.isqrt(R)) + 1
    base_primes = simple_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
    
    if L == 1:
        is_prime[0] = False
    return [L + i for i, val in enumerate(is_prime) if val]

# 示例：求1e6到1e6+100000内的素数
print(segmented_sieve(10**6, 10**6 + 100000)[:10])

✅ 判断单个超大数是否为素数：Miller-Rabin 素性测试

如果你是要判断一个超大数（比如几百位）是否为素数，那么：

Miller-Rabin 素性测试 是目前实际中最快的概率性算法。

✅ 特点：

时间复杂度：O(k log³ n)，k 是测试轮数。
可通过选择足够大的 k（如 12 轮）使误判率极低（< 2^-64）。
对于 64 位整数，确定性版本也可行（只需测试特定基）。

✅ 示例代码（Python，64位以内确定性）：

Python

复制

def is_prime(n):
    if n < 2:
        return False
    for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
        if n % p == 0:
            return n == p
    d, s = n - 1, 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
        if a >= n:
            continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

# 示例
print(is_prime(982451653))  # True

✅ 总结：你该用哪个？

表格

复制

需求	推荐算法	时间复杂度	备注
求区间素数（如 1~N）	分段筛	接近线性	实际最快
判断单个超大数	Miller-Rabin	`O(log³ n)`	实际最快
理论最优（但不可实现）	AKS 素性测试	`O(log⁶ n)`	纯理论

博客

给出一个最快的求素数的算法

✅ 最快求区间素数的算法：分段筛（Segmented Sieve）

✅ 原理：

✅ 时间复杂度：

✅ 示例代码（Python）：

✅ 判断单个超大数是否为素数：Miller-Rabin 素性测试

✅ 特点：

✅ 示例代码（Python，64位以内确定性）：

✅ 总结：你该用哪个？

全部评论

分类

热门文章

Tags

关于