质数

质数的判定

试除法：判定n是否为质数，扫描2~sqrt(n)即可，特判0和1这两个数，它们既不是质数，也不是合数。

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

质数的筛选

问题：给定一个整数n，求1~n之间的所有质数。

埃氏筛：从2开始从小到大扫描每个数x，标记它的所有倍数为合数，每当遇到一个未被标记的数，就是质数。

优化：2和3都会标记6，所以对于x，我们只需从x²开始标记即可。

复杂度O(nloglogn).接近线性，最常用。

void primes(int n) {
    memset(v, 0, sizeof(v));
    for (int i = 2; i <= n; i ++) {
        if (v[i]) continue;
        cout << i << endl;//i是质数
        for (int j = i; j <= n / i; j ++) v[i * j] = 1; 
    }
}

质因数分解

void divide(int n) {
    m = 0;
    for (int i = 2; i <= sqrt(n); i ++) {
        if (n % i == 0) {
            p[++ m] = i, c[m] = 0;
            while (n % i == 0) n /= i, c[m] ++;
        }
    }
    if (n > 1) p[++ m] = n, c[m] = 1;//n是质数
    for (int i = 1; i <= m; i ++)
        cout << p[i] << '^' << c[i] << '\n'; 
}