质数与质因数分解（一）

质数的概念与判定

若一个正整数$ N $为质数，那么不存在一个数$ M(2\le M\le \sqrt{N}) $，使得$ M $整除$ N $. 一个足够大的数$ N $之前大约有$ N / \ln{N} $个质数。
由此我们得出了判断一个数是不是质数的朴素方法:

bool isPrime(int n) {
    if (n <= 1) return false;
    int t = sqrt(n);
    for (int i = 2; i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

但是这个方法效率很低，仅仅判定一个数就达到了$ O(\sqrt{N}) $的时间复杂度，需要优化。

Miller_Robbin方法

先来回顾一下费马小定理：
如果$ p $是一个质数，$ a $是一个整数，那么有$ a^p \equiv a;(mod; p) $，如果$ a $不是$ p $的倍数，那么$ a^{p-1} \equiv 1;(mod; p) $.
依据费马小定理，我们只需遍历小于$ p $的数，并判断上述第二个式子是否成立即可，但是这样复杂度甚至比刚才的朴素判断方法还要低。事实上，可以证明的是，对于一个小于$ p $的数，我们每进行一次判断，我们至少排除了p不是素数的一半的可能性。于是，我们只需选取一个合适的数量，比如判断100次，那么此时p不是素数的概率只有$ (1/2)^{100} $，这个概率已经足够说明p就是一个素数了。在计算次方的时候，使用快速幂，记得随时取模。

int modpow(long long x, int n, int mod) {
    int y = 1;
    while (n != 0) {
        if (n & 1) y = (y * x) % mod;
        x = (x * x) % mod;
        n >>= 1;
    }
    return y;
}

bool isprime(int p) {
    int epochs = std::min(p >> 1, 100);
    for (int i = 0; i < epochs; i++) {
        int a = rand() % (p - 2) + 2;      
        if (modpow(a, p - 1, p) != 1)
            return false;
    }
    return true;
}

该算法的时间复杂度为$ O(C\log^{2}{N}) $，其中$ C $为选取的判断次数。

Eratosthenes筛法

对于少量质数的判断，使用上面的方法比较好，但是如果一次需要使用大量的素数，使用上面的方法，就显得效率非常低了。考虑这样一个问题：求出$ 1-N $之间的所有素数。对于这个问题，我们不可能一个个数去检查。Eratosthenes筛法的思想很简单，就是一个数的倍数一定不是质数。所以从2开始扫描每个数，标记它的所有倍数为不是素数即可。

void getprimes(int n) {
    isprime[0] = isprime[1] = false;
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= n / i; j++)
            isprime[i * j] = false;
    }
}

对于Eratosthenes筛法，有两个简单的优化，一个是对于一个数，只需要用素数去筛去即可，另外一个是，当前数的平方之前的数，一定已经被筛选过了。优化后的代码如下：

void getPrimes(int n) {
    isprime[0] = isprime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (isprime[i]) continue;
        for (int j = i; j <= n / i; j++)
            isprime[i * j] = false;
    }
}

代码的时间复杂度为$ O(N\log{\log{N}}) $.

Euler筛法

Eratosthenes筛法的复杂度已经非常接近线性了（~~但是我们依然不满足~~），Euler筛法基于这样一个原则，每一个数只会被它的最小质因数筛掉。先看代码，具体后面再解释。

void getPrimes(int n) {
    for (int i = 2; i <= n; i++) {
        if (isprime[i]) primes[cnt++] = i;
        for (int j = 0; j < cnt && primes[j] <= n / i; j++) {
            isprime[primes[j] * i] = false;
            if (i % primes[j] == 0) break;
        }
    }
}

别的部分好理解，但是为什么$ primes[j] $整除$ i $的时候需要跳出循环呢？我们假设$ i = k * primes[j] $，那么$ i * primes[j+1] = k * primes[j] * primes[j+1] $，也就是说，$ i * primes[j+1] $一定有一个小于$ primes[j+1] $的质数（也就是$ primes[j] $)已经或者会在之后将其筛除，这样就保证了一个数不会被多个不同的质因子重复筛选多次。
算法的时间复杂度为$ O(N) $.

Euler筛法的另一种代码实现如下，其中$ v $记录着一个数的最小质因子：

void getPrimes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!v[i]) { v[i] = i; primes[cnt++] = i; }
        for (int j = 0; j < cnt; j++) {
            if (primes[j] > v[i] || primes[j] > n / i) break;
            v[primes[j] * i] = primes[j];
        }
    }
}

质因数分解

算术基本定理：任何一个大于1的正整数可以唯一分解为有限个质数的乘积，也就是$ N = p_1^{c_1}\times p_2^{c_2}\times p_3^{c_3}\times\cdots \times p_n^{c_n} $.
我们使用最朴素的试除法来分解质因数，每次找到一个质因数，那么就不断除以这个质因数直到除尽为止。代码中的$ c $数组存放的是各个质因数的次数（对应于$ primes $数组）。

void factorize(int n) {
    int t = sqrt(n);
    for (int i = 0; i < cnt; i++) {
        if (n == 1 || primes[i] > t) break;
        while (n % primes[i] == 0) {
            n /= primes[i];
            c[i] += 1;
        }
    }
}