1. 质数的判断 质数：在大于1的整数中，如果只包含1和它本身这两个约数，就被成为质数，或者叫素数.

如果 d | n, 则(n / d) | n. ------ 可以发现n的所有约数都是成双成对出现的.

质数定理： 1 - n中有n / ln(n) 个质数.

调和级数： 1 + 1 / 2 + 1 / 3 + 1 / 4 + ··· = lnn + C(0.577)

1.朴素做法 ---- $O(n)$

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

2.改进版 ---- $O(\sqrt{n})$(一定是)

bool is_prime(int n){
    if(n < 2) return false;
    for(int i = 2; i <= n / i; i ++){//约数成对出现,i 和 n / i, 枚举到较小的那个即可. 
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

尽量不要写成： 1. for(int i = 2; i * i <= n; i ++) // 但 i 较大时, i * i 可能超出int的最大表示范围,导致结果出错. 2. for(int i = 2; i <= sqrt(n); i ++) // 反复调用sqrt()函数, 运行效率比较低

建议写成： for(int i = 2; i <= n / i; i ++) // 可以很好地规避上述情况

典型例题 试除法判定质数

1. 分解质因数 分析：假设枚举到 i, n 中一定不包含 2 ~ i - 1 之间的质因子, 又因为n % i == 0,即 n 为 i 的倍数, 所以 i 当中也不包含 2 ~ i - 1 之间的质因子, 所以 i 一定是质数. 1.朴素做法 ---- $O(n)$

void divide(int n){
    for(int i = 2; i <= n;  i ++){
        if(n % i == 0){
            int s = 0;
            while(n % i == 0){
                n /= i;
                s ++;
            }

            cout << i << ' ' << s << endl;
        }
    }
}

2.改进版 ---- $O(\sqrt{n})$(不一定)

void divide(int n){
    for(int i = 2; i <= n / i; i ++){//n中最多包含一个大于sqrt(n)的质因子
        if(n % i ==0){
            int s = 0;
            while(n % i == 0){
                n /= i;
                s ++;
            }
            cout << i << ' ' << s << endl;
        }
    }
    if(n > 1) cout << n << ' ' << '1' << endl;//大于sqrt(n)的质因子
}

注意：当 $n = 2^k$ 时, 时间复杂度为 $logn$, 因此其时间复杂度介于 $logn ~ \sqrt{n}$ 之间

典型例题 分解质因数

1. 筛质数 1.朴素做法 ----$O(n∗logn)$

原理: 2 - p - 1中的数都没有把 p 删掉,说明 p 不是 2 - p - 1 当中任何一个数的倍数,因此 p 是一个质数.

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n){
    for(int i = 2; i <= n; i ++){
        if(!st[i]) primes[cnt ++] = i;
        for(int j = i + i; j <= n; j += i){//依次删掉每个i的倍数
            st[j] = true;
        }
    }
}

2.改进版 ---- $O(n∗loglogn)$ (埃氏筛法)

质数定理：1 - n 当中, 有 n / ln(n) 个质数.

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n){
    for(int i = 2; i <= n; i ++){
        if(!st[i]){
            primes[cnt ++] = i;
            for(int j = i + i; j <= n; j += i){//只删掉质数i的倍数
                st[j] = true;
            }
        }
    }
}

2.终极版 ---- $O(n)$ (线性筛法)

核心：每个 n 只会被它的最小质因子筛掉.

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n){
    for(int i = 2; i <= n; i ++){
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; primes[j] <= n / i; j ++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;//primes[j]一定是i的最小质因子
        }
    }
}

分析： 1.i % primes[j] == 0, 说明：primes[j]一定是i的最小质因子,primes[j]一定是primes[j] * i的最小质因子 2.i % primes[j] != 0, 说明: primes[j]一定小于i的所有质因子,primes[j]一定是primes[j] * i的最小质因子 综上：primes[j]一定是primes[j] * i的最小质因子.

我们用最小质因子筛,而每个数只有一个最小质因子,因此每个数只会被筛一次,所以是线性的.

注意：如果在1e6左右,埃氏筛法和线性筛法差不多,但在1e7左右,线性筛法要比埃氏筛法快几倍.在实际应用中线性筛法用的比较多,埃氏筛法用的较少,但埃氏筛法的思想很重要.

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com