素数

试除法判断素数

判断x是否为素数，只需要枚举2到$\sqrt{x}$的所有整数，如果存在整数可以被x整除，那么x就是合数，否则就是素数

bool is_prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= x/i; i++)
        if (x%i == 0) return false;  // 存在整数i可以被x整除
    return true;
}

试除法分解素因数

将x分解为若干素数的乘积，采用试除法，发现素因数i后，将x除以i若干次直到不再能够整除，循环结束后还剩最后一个素因数

for (int i = 2; i <= x/i; i++) {
    if (x%i == 0) {  // i是x的素因数
        int c = 0;
        while (x%i == 0) {
            x /= i;
            c++;
        }
        // 得到素因数i，指数为c
    }
}
if (x > 1)
    // 得到素因数x，指数为1

筛法求素数

朴素筛法求素数

求小于等于x的所有素数，isPrime数组标记是否为素数，初始化为全true，发现素数后，将其所有倍数都标记为合数

for (int i = 2; i <= x; i++) {
    if (isPrime[i]) {
        // i是素数
        for (int j = 2; j <= x/i; j++)
            isPrime[i*j] = false;
    }
}

朴素筛法还有另一种写法，用primes数组存储所有已知素数，cnt标记已知数组个数（即primes数组大小，初始化为0），外循环的i不仅用来寻找素数，而且用来作为系数，将已知素数$\times$当前系数（即对应倍数）都标记为合数

for (int i = 2; i <= x; i++) {
    if (is_prime[i]) primes[cnt++] = i;  // i是素数
    for (int j = 0; j < cnt && primes[j] <= x/i; j++)
        is_prime[i*primes[j]] = false;
}

线性筛法求素数

线性筛法保证每个合数只会被它的最小素因数筛一次，当i % primes[j] == 0时，primes[j]是i*primes[j]的最小素因数，primes[j]之后的素数记为primes[j+]，此时i*primes[j+]的最小素因数是primes[j]，已经被最小素因数标记过，所以可以break

for (int i = 2; i <= x; i++) {
    if (is_prime[i]) primes[cnt++] = i;  // i是素数
    for (int j = 0; j < cnt && primes[j] <= x/i; j++) { // 线性筛法中j<cnt这个判断条件其实可以不写，但是朴素筛法中必须写
        is_prime[i*primes[j]] = false;
        if (i % primes[j] == 0) break;
    }
}

---