埃拉托斯特尼筛法#

埃拉托斯特尼筛法（Sieve of Eratosthenes）简称埃筛或埃式筛法，这个方法历史悠久，早在公元前2世纪就被埃拉托斯特尼提出了。

其算法的主要思想是：如果一个数字$p$是素数，那么它的倍数就都不是素数。我们从2枚举到n，2是素数，因此划掉所有2的倍数。如果一个数字在被枚举到时，还没有被划掉，那么就说明这个数是素数。下面这张图很好的展示了这个过程。

1
def sieveOfEratosthenes(n):
2
    prime = [True for _ in range(n+1)]
3
    p = 2
4
    while (p * p <= n):
5
        if (prime[p] == True): # if p is prime
6
            for i in range(p * 2, n+1, p): # mark all multiples of p as not prime
7
                prime[i] = False
8
        p += 1
9
    prime[0] = False
10
    prime[1] = False
11
    return prime

欧拉筛#

埃式筛法还是有进步的空间，因为埃筛在划掉数字的时候可能会发生很多重复。比如对于数字6，它即是2的倍数，又是3的倍数。如果能避免这种重复，那么每个数字就只需要划掉一遍就可以了，这样我们能得到一个线性复杂度的筛法。这个方法最早被莱昂哈德·欧拉发现，所以被称为欧拉筛。

1
def sieveOfEuler(n):
2
    isPrime = [True for _ in range(n+1)]
3
    Prime = []
4
    for i in range(2, n+1):
5
        if isPrime[i]:
6
            Prime.append(i)
7
        for pri in Prime:
8
            if i * pri > n:
9
                break
10
            isPrime[i * pri] = False
11
            if i % pri == 0:
12
                break
13
    return Prime

费马素性测试#

费马素性测试是一种概率素性测试，它主要使用的数学原理是费马小定理。

费马小定理说：如果一个数字p是素数，那么对于任意不能被p整除的自然数a来说，满足下式：

$a^{p-1}\equiv 1\mod p$

那么我们如果发现一个这样的a，不满足上面的式子，那么我们就可以肯定p一定不是一个素数，而是一个合数。而如果p通过了一次或多次这样的测试，我们称之为 费马伪素数，之所以叫做伪素数是因为费马测试不能保证通过测试的数字一定是素数。

考虑到以下两个情况：1、如果$a\equiv 1 \mod p$，那么费马小定理一定成立。2、如果$a\equiv -1 \mod p$，那么如果p是奇数，费马小定理一定成立，而素数中只有2一个偶数。因此，我们在挑选a时，不需要考虑这两种情况。

一般来说，选择范围是$1\lt a\lt p-1$。如果我们选择的a满足$gcd(a, p)=d>1$，那么显然此时p不是一个素数（p有因子$d=gcd(a, p)$）也可以证明此时费马小定理不成立，证明如下：

从区间$[2, p-1)$选出一个自然数a，并且$gcd(a, p)=d>1$。假设a、p满足费马小定理，即$a^{p-1}\equiv 1\mod p$，存在整数k满足$a^{p-1}-pk=1$，因为$a|d, p|d$，所以$0\equiv 1 \mod d$，而此式仅当d=1时成立，由反证法可知a、p不满足费马小定理。

但如果我们仅选择满足$gcd(a, p)=1$的数字a，即使对于所有这样的a，p都能通过费马测试，也不能保证p就一定是素数，这类数字被称为 卡迈克尔数（Carmichael number），定义为：

在数论上，卡迈克尔数是合数n，对于任意与n互质的数字a，满足$a^{n-1}\equiv 1\mod n$

最小的卡迈克尔数是$561=3\times 11\times17$。但其实不用很担心，因为卡迈克尔数非常的稀疏，$10^{16}$之内只有246683个，相对于这个范围来说是非常少的。不过为了保证算法的正确性，我们还是不能仅仅判断$gcd(a, p)=1$的情况。

那么我们进一步思考，是否有对于区间$[2, p-1)$中的所有的a，对满足费马小定理的伪素数n呢？

其实这是不可能的，因为如果n不是素数，那么区间$[2, p-1)$一定有其因数d，当a取得d时，根据上面的证明，费马小定理一定不成立。因此，我们可以保证，枚举所有的a，一定能验证一个数字是否为素数。

但是枚举所有的a，这个算法的时间复杂度为$O(n\log n)$，甚至超过了试除法的$O(\sqrt n)$，这显然不是我们想要的结果。如果我们能够知道一个数字通过费马测试的可能性有多高，那么我们就可以多次选择不同的a来进行费马测试，一定有一次没能通过费马测试，那么就说明这个数字a不是一个素数。

其实有如下结论：

如果n至少有一个与其互质的a能证明它不是伪素数，也就是说如果n不是卡迈克尔数，那么在与其互质的a中，至少有一半能证明n不是一个伪素数，也就是说n是一个合数。

那么一次费马测试的通过率就是50%，如果我们多次进行测试就可以把概率降低至我们能接受的范围。如果测试k次，这个算法的时间复杂度就是$O(k\log n)$

1
def fermatPrimailtyTest(n, k):
2
    if n == 2:
3
        return True
4
    if n % 2 == 0:
5
        return False
6
    for _ in range(k):
7
        a = random.randint(2, n - 1)
8
        if pow(a, n - 1, n) != 1:   # Fermat's little theorem
9
            return False
10
    return True

米勒-拉宾素性测试#

费马测试在数字较小的时候准确性尚可，但是当数字大到一定程度（$2^{64}$）或遇到卡迈克尔数时，准确性就不尽人意了。

米勒-拉宾素性测试方法由米勒（Gary L. Miller）在1976年提出，但原始的算法是确定型检测方法，并且正确性依赖于未被证明的扩展黎曼猜想（extended Riemann hypothesis）拉宾（Michael O. Rabin）在1980年将其修改为无条件的概率型检测方法。

在将米勒-拉宾测试的原理之前，我们需要先介绍几个引理。

1
def MillerRabinPrimalityTest(n, k):
2
    if n == 2:
3
        return True
4
    if n % 2 == 0:
5
        return False
6
    r, s = 0, n - 1
7
    while s % 2 == 0:
8
        r += 1
9
        s //= 2
10
    for _ in range(k):
11
        a = random.randrange(2, n - 1)
12
        x = pow(a, s, n)
13
        if x == 1 or x == n - 1:
14
            continue
15
        for _ in range(r - 1):
16
            x = pow(x, 2, n)
17
            if x == n - 1:
18
                break
19
        else:
20
            return False
21
    return True

确定素性测试#

确定型素性测试不是本篇内容的重点，比较出名的一个确定型测试是AKS素性检测，由Manindra Agrawal, Neeraj Kayal, and Nitin Saxena在2002年提出，如果有兴趣大家可以自己研究一下。