素数¶

判断素数¶

试除法¶

均值优化¶

再次阅读合数的定义：

除了 1 和其本身外具有其他正因数的正整数

容易知道，对任一合数 $A$ ，一定存在两个正因子 $M\ ,\ N$ 满足 $A=M×N$ ，又由均值不等式可知 $M\ ,\ N$ 中一定一个 $≥\sqrt{A}$ ，一个 $≤\sqrt{A}$

所以一个数 $A$ 如果在 $(\ 1\ ,\ \sqrt{A}\ ]$ 内找不到因子，那在 $[\ \sqrt{A}\ ,\ A\ )$ 内也不可能有因子，即可判断 $A$ 为素数

素数筛法¶

埃氏筛¶

Eratosthenes 筛法，埃拉托斯特尼筛法，简称 埃氏筛法

时间复杂度：$O(n\log\log n)$

vector Eratosthenes(int n){
    bool is_prime[n+1];
    vector<int> primes;
    fill(is_prime,is_prime+n+1,true);
    // 用 fill 而不是 memset 初始化，memset 只能初始化为 0,-1
    for(int i=2;i<=sqrt(n);i++){
    // 筛到 sqrt(n) 即可，大于 sqrt(n) 的数根本不会进内层循环
        if(flag[i]){
            primes.push_back(i); // 加入素数表
            for(int j=i*i;j<=n;j+=i){
            // 2 到 i-1 的倍数已经筛过了，直接从 i 的倍数开始筛
                flag[i]=false;
            }
        }
    }
    return primes;
}

欧拉筛¶

在埃氏筛法的基础上，让每个合数只被其 最小质因数 筛去

时间复杂度：$O(n)$ （线性时间复杂度，故欧拉筛也称 线性筛）

从 2 开始遍历，并维护一个素数表（初始为空）

$2\ \ \ \ \ 3\ \ \ \ \ 4\ \ \ \ \ 5\ \ \ \ \ 6\ \ \ \ \ 7\ \ \ \ \ 8\ \ \ \ \ 9\ \ \ \ \ 10\\ \mathrm{primes}:(\ )$

遍历到 2，未被标记（没有变灰），将其放入素数表中

$(2)\ \ \ \ \ 3\ \ \ \ \ 4\ \ \ \ \ 5\ \ \ \ \ 6\ \ \ \ \ 7\ \ \ \ \ 8\ \ \ \ \ 9\ \ \ \ \ 10\\ \mathrm{primes}:(2,)$

用 2 去乘质数表里的每个数，标记所得数（标记了 $2×2=4$）

$(2)\ \ \ \ \ 3\ \ \ \ \ {\color{lightgray}4}\ \ \ \ \ 5\ \ \ \ \ 6\ \ \ \ \ 7\ \ \ \ \ 8\ \ \ \ \ 9\ \ \ \ \ 10\\ \mathrm{primes}:(2,)$

遍历到 3，未被标记，将其放入素数表中，并标记 6，9

$2\ \ \ \ \ (3)\ \ \ \ \ {\color{lightgray}4}\ \ \ \ \ 5\ \ \ \ \ {\color{lightgray}6}\ \ \ \ \ 7\ \ \ \ \ 8\ \ \ \ \ {\color{lightgray}9}\ \ \ \ \ 10\\ \mathrm{primes}:(2,3,)$

遍历到 4，已被标记，不将其放入素数表中，先标记 $4×2=8$ ，但发现 4 能被 2 整除，于是不继续标记，直接遍历下一个数 $5$

$2\ \ \ \ \ 3\ \ \ \ \ ({\color{lightgray}4})\ \ \ \ \ 5\ \ \ \ \ {\color{lightgray}6}\ \ \ \ \ 7\ \ \ \ \ {\color{lightgray}8}\ \ \ \ \ {\color{lightgray}9}\ \ \ \ \ 10\\ \mathrm{primes}:(2,3,)$

Warning

标记 i*primes[j] 时，如果发现 i%primes[j]==0 ，则不再标记 i*primes[j+1]

因为 i%primes[j]==0 说明 i 中有 primes[j] 这个质因子，那么 i*primes[j+1] 中也肯定有 primes[j] 这个质因子，而 i>primes[j]，所以 i*primes[j+1] 应该由最小的质因子 primes[j] 而不是当前质因子 i 去筛掉

就拿 4 为例，4%2==0 说明 4 中有 2 这个质因子，那么 4×3=12 中也有 2 这个质因子，所以 12 应该在后面遍历到 6 时由 6×2=12 筛掉，而不是现在用 4 筛掉

$2\ \ \ \ \ 3\ \ \ \ \ {\color{lightgray}4}\ \ \ \ \ (5)\ \ \ \ \ {\color{lightgray}6}\ \ \ \ \ 7\ \ \ \ \ {\color{lightgray}8}\ \ \ \ \ {\color{lightgray}9}\ \ \ \ \ {\color{lightgray}10}\\ \mathrm{primes}:(2,3,5,)$

$2\ \ \ \ \ 3\ \ \ \ \ {\color{lightgray}4}\ \ \ \ \ 5\ \ \ \ \ ({\color{lightgray}6})\ \ \ \ \ 7\ \ \ \ \ {\color{lightgray}8}\ \ \ \ \ {\color{lightgray}9}\ \ \ \ \ {\color{lightgray}10}\\ \mathrm{primes}:(2,3,5,)$

$2\ \ \ \ \ 3\ \ \ \ \ {\color{lightgray}4}\ \ \ \ \ 5\ \ \ \ \ {\color{lightgray}6}\ \ \ \ \ (7)\ \ \ \ \ {\color{lightgray}8}\ \ \ \ \ {\color{lightgray}9}\ \ \ \ \ {\color{lightgray}10}\\ \mathrm{primes}:(2,3,5,7,)$

$2\ \ \ \ \ 3\ \ \ \ \ {\color{lightgray}4}\ \ \ \ \ 5\ \ \ \ \ {\color{lightgray}6}\ \ \ \ \ 7\ \ \ \ \ ({\color{lightgray}8})\ \ \ \ \ {\color{lightgray}9}\ \ \ \ \ {\color{lightgray}10}\\ \mathrm{primes}:(2,3,5,7,)$

$2\ \ \ \ \ 3\ \ \ \ \ {\color{lightgray}4}\ \ \ \ \ 5\ \ \ \ \ {\color{lightgray}6}\ \ \ \ \ 7\ \ \ \ \ {\color{lightgray}8}\ \ \ \ \ ({\color{lightgray}9})\ \ \ \ \ {\color{lightgray}10}\\ \mathrm{primes}:(2,3,5,7,)$

$2\ \ \ \ \ 3\ \ \ \ \ {\color{lightgray}4}\ \ \ \ \ 5\ \ \ \ \ {\color{lightgray}6}\ \ \ \ \ 7\ \ \ \ \ {\color{lightgray}8}\ \ \ \ \ {\color{lightgray}9}\ \ \ \ \ ({\color{lightgray}10})\\ \mathrm{primes}:(2,3,5,7,)$

实现¶

vector Euler(int n){
    bool is_prime[n+1];
    vector<int> primes;
    fill(is_prime,is_prime+n+1,true);
    for(int i=2;i<=n;i++){
        if(is_prime[i]){
            primes.push_back(i);
        }
        for(int p:primes){
            if(i*p>n) break;
            is_prime[i*p]=false;
            if(i%p==0) break;
        }
    }
    return primes;
}

素数¶

相关概念¶