质数测试与筛选

质数也称素数，指大于1的自然数中，除了1和它本身外不再有其他因数的数。

正整数按素性可以分为1，质数和合数。

小质数测试

判断一个数n是否为质数，只需要检查2~sqrt(n)中的数能否被n整除即可，时间复杂度为O(sqrt(n))。

int IsPrime(int n) {
    if (n < 2) return 0;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return 0;
    return 1;
}

大质数测试

如果要测试的数n非常大，一般采用概率算法来做。

首先介绍简单的Fermat素性测试方法，该方法基于费马小定理：对于正整数a, n，如果有a ^ (n-1) % n = 1，那么n大概率为质数，否则一定是合数。一般多选几个a进行测试，测试次数越多，误判的可能性就越小。

def is_prime(n, t=100):
    if n < 2: return False
    for _ in range(t):
        x = random.randint(1, n-1)
        if pow(x, n-1, n) != 1:
            return False
    return True

Miller-Rabin素性测试则在Fermat素性测试的基础上做了进一步优化：如果n是奇质数，则x ^ 2 % n = 1的解为：x=1或p-1 (mod n)。

def is_prime(n, t=20):
    if n < 2: return False
    d = n-1
    while d % 2 == 0: d //= 2
    for _ in range(t):
        a = random.randint(1, n-1)
        x = pow(a, d, n)
        while d < n:
            y = pow(x, 2, n)
            if y == 1 and x != 1 and x != n - 1:
                return False
            x = y
            d = d * 2
        if x != 1:
            return False
    return True

质数筛选

常用的筛法有埃氏筛和欧拉筛，以下是埃氏筛的参考代码，其中外层循环可优化到只枚举[2, sqrt(n)]，不做优化也足够快，时间复杂度为O(nloglogn)。

int a[1000005];
void siftp(int n) {
    a[0] = a[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (a[i]) continue;
        for (int j = 2 * i; j <= n; j += i)
            a[j] = 1;
    }
}

欧拉筛选法用于获取1~N之间的所有质数，该方法相比于埃氏筛法有两处改进：

• 外层枚举i时，只枚举i的质数倍。
• 在从小到大依次枚举质数p来计算i的倍数时，增加检查p|i，如果成立，则停止枚举。

正是由于这两处改进，使得每个合数只会被枚举到一次，时间复杂度为O(n)。

int a[1000005], p[100005], pn;
void siftp(int n) {
    a[0] = a[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!a[i]) p[pn++] = i;
        for (int j = 0; j < pn; j++) {
            if (i * p[j] > n) break;
            a[i*p[j]] = 1;
            if (i % p[j] == 0) break;
        }
    }
}