每个人都可以，
拥有SSL证书

前阵子写个小脚本生成 RSA 密钥对，第一步就是找大素数。翻了下以前收藏的代码，发现大多数人写的还是从 2 循环到 n-1 那个版本。逻辑没毛病，但跑一个十二位的数要二十秒往上，等得人怀疑人生。

这类优化看着基础，真写起来细节不少。把常用的版本和踩过的坑整理一下，数据都是在本机 Python 3.13 上实测的。

一开始谁都这么写

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

n 取 1000003，本机跑一次 46.7 毫秒。听上去还行，但这是个七位数。放到循环里调几千次，或者数再大两个量级，就没法看了。

只查到平方根

如果 n 能拆成 a × b，而且 a ≤ b，那 a 一定不会超过 √n。所以在 √n 以里找不到因子的话，后面也不用找了。

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

同样那个 1000003，耗时从 46.7 毫秒掉到 0.0725 毫秒，六百多倍。

这里有个小选择：循环条件写 i * i <= n，还是先算出 √n 存成 limit 再比。我一般写前者，全程整数运算，不用担心精度。后面会说为什么这件事值得在意。

偶数直接排除

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

0.0371 毫秒。比上一版又快了接近一倍。

6k±1 这一步

大于 3 的素数一定长成 6k-1 或 6k+1 的样子。

理由拆开看很简单。任何整数除以 6，余数只有 0 到 5 这六种。余数 0、2、4 说明它是偶数，余数 3 说明能被 3 整除，全部排除掉。能剩下的只有余数 1 和余数 5，而 6k+5 就是 6(k+1)-1。

所以候选因子只剩 5、7、11、13、17、19 这一串，步长在 2 和 4 之间来回跳。

def is_prime(n):
    if n < 2:
        return False
    if n in (2, 3):
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

一次循环测两个候选，步长 6，等于每六个数里只测两个。1000003 这个数上跑到 0.0207 毫秒，比最初的暴力版快了两千两百倍左右。

换成 isqrt 的写法

Python 3.8 之后有 math.isqrt，返回整数平方根并向下取整，整个计算不碰浮点。配合 range 的步长参数，代码还能再短一点：

import math

def is_prime(n):
    if n < 2:
        return False
    if n in (2, 3):
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    for i in range(5, math.isqrt(n) + 1, 6):
        if n % i == 0 or n % (i + 2) == 0:
            return False
    return True

实测 0.0164 毫秒，比 while 版还快一点，因为 range 的迭代在 C 层完成，Python 层的循环体只负责取模判断。

顺带说下为什么不建议用 int(n ** 0.5)。

float 只有 53 位有效精度，n 超过 2 的 53 次方之后，它被转成浮点时就已经不是原值了。我试过随机生成几百万个大数去撞「开方后取整偏小」的用例，一个没撞上，所以这个坑多半只在极端边界上才出现。但另一件事是实打实的：

>>> (10 ** 400) ** 0.5
OverflowError: int too large to convert to float

n 再大一点，n ** 0.5 会直接抛异常。

math.isqrt 对任意大的整数都正常返回。写密码学相关的代码时，输入位数往往就是奔着几百位去的，这个差别不能忽略。

这版就够了吗

看场景。

前面那组数据都是在「判断单个数」的前提下测的。

需求一旦变成「找出 100 万以内的所有素数」，逐个调用这个函数要 1.24 秒，换成埃氏筛只要 0.004 秒，差三百倍。筛法的思路是反过来的，不去问这个数是不是素数，而是从已知素数出发把它的倍数全部划掉。

import math

def sieve(n):
    flags = bytearray([1]) * (n + 1)
    flags[0:2] = b'\x00\x00'
    for i in range(2, math.isqrt(n) + 1):
        if flags[i]:
            flags[i*i::i] = bytearray(len(flags[i*i::i]))
    return flags

用 bytearray 存标记而不是 list，内存占用和切片赋值都快不少。

最后那行 len(flags[i*i::i]) 看着绕，其实只是为了算出切片长度好生成等长的零字节，把这段批量置 0。

大数别用试除

试除是 O(√n)。n 等于 10 的 12 次方时是 20 毫秒，10 的 18 次方就变成二十秒上下，2 的 61 次方减 1 那种级别估计得跑一分钟。

生成 RSA 密钥要的是几百位的素数，这条路走不通。

这种规模用 Miller-Rabin。它是概率算法，但把轮数堆上去，出错概率可以压到忽略不计。

import random

def is_prime_mr(n, rounds=20):
    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 = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for _ in range(rounds):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = x * x % n
            if x == n - 1:
                break
        else:
            return False
    return True

能跑这么快靠的是 pow(a, d, n) 这个三参数形式，Python 内部走模幂快速算法，不会先把那个天文数字算出来再取模。

2 的 61 次方减 1 用这个判断，0.35 毫秒出结果。

不想自己写也有现成的，sympy 里的 isprime 直接用，实现是 Miller-Rabin 加一组确定性基底的组合，比随手写的版本稳。

一个容易忽略的点

n in (2, 3) 那行别漏。少了它，2 和 3 会在后面的 n % 2 == 0 那步被误杀。我第一次把这段压缩成一行的三元表达式时，就是这么把 3 判成合数的，查了半天才反应过来。

负数、0、1 这几个输入，函数开头那句 n < 2 一次性挡掉，比在调用方判断省心。

顺带

素数这东西平时不太想起，真要用基本都在密码学场景里，RSA 密钥、Diffie-Hellman 参数，底层都是大素数。

前阵子给内部几个服务换 HTTPS，证书是在 lcjmSSL 上申请的，泛域名和多域名都支持，走 ACME 自动签发，背后是 Let's Encrypt、Google Trust Services、ZeroSSL 这几家。它有 API，续期能直接挂到 CI 里，不用设日历提醒手动去点。证书过期这种事一旦忘了，半夜报警挺折腾的。

说回正题，判断素数本身不难，难的是在不同规模下选对方法：几十万以内随便写，上百万批量用筛，上了大数换 Miller-Rabin。

写之前先想清楚输入大概多大，比事后调循环省事得多。