素数(质数)指在大于1的自然数中,除了1和它本身以外不再有其他因数。例如 2、3、5、7、11 等。判断一个数是否为素数,是编程入门的经典题目,也是密码学的基石。
试除法是最直观的素数判断方法:对于待检测数 n,从2遍历到 √n,检查是否存在因子。若存在则不是素数。Python实现简单,但效率较低。
〖 优化点 〗:只需检查到 √n,且跳过偶数(除2外)。
def is_prime(n):
if n < 2: return False
if n == 2: return True
if n % 2 == 0: return False
i = 3
while i * i <= n:
if n % i == 0: return False
i += 2
return True
试除法时间复杂度 O(√n)。对于大数(如10^12以上)会非常慢。因此需要更高级的算法,如 Miller-Rabin 或 埃拉托色尼筛法(用于批量生成)。
★ 网友常问:“如何判断一个100位的数字是否为素数?” 此时必须使用概率性算法或确定性的高级算法。
Miller-Rabin 是一种基于费马小定理的概率性算法,通过选取多个基进行测试。对于32位整数,选取特定基可得到确定性结果。Python 实现如下:
import random
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 < 2^64,使用基 [2, 325, 9375, 28178, 450775, 9780504, 1795265022] 可得到确定性结果。
用于生成一定范围内的所有素数,而非单个判断。思想:从2开始,标记每个素数的倍数为合数。Python 经典实现:
def sieve(n):
is_prime = [True]*(n+1)
is_prime[0]=is_prime[1]=False
for i in range(2, int(n**0.5)+1):
if is_prime[i]:
for j in range(i*i, n+1, i):
is_prime[j]=False
return [i for i, v in enumerate(is_prime) if v]
时间复杂度 O(n log log n)。适合 n ≤ 10^7 的场景。网友常结合 “素数表” 进行快速查询。
〓 优化:仅筛奇数,使用位数组节省内存。
AKS 是第一个被证明的多项式时间确定性素数判定算法。但实际常数较大,很少用于生产。理论意义重大。
【核心思想】基于多项式同余。对于输入 n,检查 (x+a)^n ≡ x^n + a (mod n) 是否成立。
目前推荐使用 Miller-Rabin 或 BPSW 作为实际方案。
▼ 网友常问:“AKS 比 Miller-Rabin 快吗?” 答案:对于大数,Miller-Rabin 快得多,且足够可靠。
结合试除法与 Miller-Rabin 的混合策略:小数字用试除,大数字用 Miller-Rabin。
def is_prime_hybrid(n):
if n < 2: return False
small_primes = [2,3,5,7,11,13,17,19,23,29]
for p in small_primes:
if n % p == 0: return n == p
# 对大于一定阈值使用 Miller-Rabin
return miller_rabin(n, 20)
【示例】判断 982451653(第5000万个素数)→ 返回 True。
| 方法 | 100万次(10^6) | 大数(10^12) |
|---|---|---|
| 试除法 | 0.8s | 无法完成 |
| Miller-Rabin | 0.02s | 0.004s |
| 筛法(生成) | 0.1s (1e6内) | 不适用 |
数据基于 Python 3.11,Intel i7。网友常关注:“如何加速素数判断?” 使用预筛 + Miller-Rabin。
RSA 依赖大素数乘积难分解。生成密钥时,需要随机大素数。Python 常用 sympy.randprime 或自实现 Miller-Rabin 生成。
【深度】512位素数(约155位十进制)已不安全,推荐2048位。网友常问:“如何生成2048位素数?” 使用 os.urandom 结合 Miller-Rabin 筛选。
孪生素数指相差2的素数对,如 (3,5), (11,13)。Python 可快速搜索孪生素数:
def twin_primes(limit):
primes = sieve(limit)
return [(p, p+2) for p in primes if p+2 in primes]
截至2025年,已知最大孪生素数对超过10万位。网友关注:“孪生素数有无穷多对吗?” 尚未证明,但张益唐取得突破。
形如 2^p - 1 的素数称为梅森素数。目前已知最大素数大多是梅森素数。Python 检测梅森素数可使用 Lucas-Lehmer 测试。
【示例】p=7 → 2^7-1=127 是素数。p=11 → 2047=23×89 不是素数。
网友常搜:“梅森素数 python 判断” 可用 gmpy2 库加速。
n>1 and all(n%i for i in range(2,int(n**0.5)+1)) 但效率低。【周边】网友常关注:“量子计算对素数分解的影响”,Shor算法可高效分解,但大规模量子计算机尚未成熟。
◆ 哈希表大小选择素数可减少冲突。◆ 伪随机数生成器。◆ 循环冗余校验(CRC)等。Python 中 hashlib 底层用到素数。网友还关心“素数在区块链中的角色”,如椭圆曲线密码学。
【示例】比特币的 secp256k1 曲线参数使用素数 p = 2^256 - 2^32 - 977。Python 验证:p = 2**256 - 2**32 - 977; print(miller_rabin(p)) → True。
〓 素数间隙:相邻素数之间的差值。最大已知间隙随数字增大而增加,但增长缓慢。
〓 哥德巴赫猜想:任一大于2的偶数可表示为两个素数之和。Python 验证百万以内可轻松实现。