筛法求素数

当只需要判断某个数是不是素数的时候，我们可以直接通过素数的定义来求，但是如果要求某个范围内的素数的个数的时候这个方法就不太合适了。虽然我们可以进行预处理，但是这种方法比较慢，一旦范围过大，预处理过程便会超时。这时候就引入了一种新的简单检定素数的方法-----埃拉托斯特尼筛法

埃拉托斯特尼筛法

从2开始，将每个素数的各个倍数(一倍除外)，标记成合数。一个素数的各个倍数，是一个差为此素数本身的等差数列。此为这个筛法和试除法不同的关键之处，后者是以素数来测试每个待测数能否被整除。埃拉托斯特尼筛法（英语：sieve of Eratosthenes ），简称埃氏筛，也称素数筛。这是一种简单且历史悠久的筛法，用来找出一定范围内所有的素数。埃拉托斯特尼筛法是列出所有小素数最有效的方法之一。

算数基本定理

每个整数 n >= 2 可唯一分解成素数乘积 n = p1p2…pr.

普通线性筛法

由算数基本定理可知，任何一个大于等于 2 的数，都可以表示成两个数相乘的形式，只有 1 和 它本身这一对组合的是素数，剩下的都是合数。对于一个合数 a，则一定等于某个素数 b 与另一个素数或者合数 c 相乘。也就是换句话说，通过筛掉所有素数的倍数，就可以将所有的合数筛掉而只剩下素数，于是有了如下的普通线性筛法。

#include <stdio.h>
#include <string.h>

#define MAX (int)1e5  //待判断素数范围0~MAX
#define ll long long
 
ll prime[MAX + 1], cnt;                                                              
bool isPrime[MAX + 1];

void init_prime()
{
    cnt = 1;
    memset(isPrime, 1, sizeof(isPrime));
    isPrime[0] = isPrime[1] = 0;
    
    for (ll i = 2; i <= MAX; i++) {
        if (!isPrime[i]) continue;//跳过合数
        prime[cnt++] = i;//保存素数
        for (ll j = 2 * i; j <= MAX; j += i)
            isPrime[j] = 0;//素数倍数都不是素数
    }
}

int main()
{   
    init_prime();
    for (ll i = 1; i < cnt; i++)
        printf("%lld%s", prime[i], i == cnt - 1 ? "\n" : " ");
    return 0;
}
           

快速筛法

再次思考普通线性筛法，一个合数 n = p1p2…pr.(pi都是素数，1 <= i <= r>),是p1的倍数，也是p2的倍数，……也是pr的倍数，换句话说，该合数被重复筛了 r 次。显然，最好的结果是每个合数只被筛一次，算法是线性的时间。那么该如何去做呢？

一种解决办法是约定每次只在 pmin 处，对该合数 n 做筛除。

#include <stdio.h>
#include <string.h>

#define MAX (int)1e2
#define ll long long
 
ll prime[MAX + 1], cnt;                                                              
bool isPrime[MAX + 1];

void init_prime()
{
    cnt = 1;
    memset(isPrime, 1, sizeof(isPrime));
    isPrime[0] = isPrime[1] = 0;

    for (ll i = 2; i <= MAX; i++) {
        if (isPrime[i]) 
            prime[cnt++] = i;  //位置1
        for (ll j = 1; j < cnt && i * prime[j] <= MAX; j++) {
            isPrime[i * prime[j]] = 0; //位置2
            if (!(i % prime[j])) break; //位置3
        }
    }
}

int main()
{   
    init_prime();
    for (ll i = 1; i < cnt; i++)
        printf("%lld%s", prime[i], i == cnt - 1 ? "\n" : " ");
    return 0;
}
           

这个算法可以保证每个数字都只被标记一遍，实现方法如下：

对于所有大于1的数，分为素数和合数，而合数又分为：

1. 一个素数乘以一个素数
2. 一个素数乘以一个合数

在位置 1，得到了所有素数，在位置 2 标记了所以合数。

在位置 2 的时候，又分为两种可能:

1. i 是素数，prime[j] 是素数
2. i 是合数，prime[j] 是素数

如上解释了为何可以标记合数

那么是如何不重复标记合数的呢？

对于 n = pmin * c, 更具最小约定应该有 c >= pmin，反过来即是每次拎一个数 c’,只需要到小于等于它的素数范围做乘法筛除即可。可是我们发现，依然会出现 34 = 26 这样的重复筛除，该如何避免这样的重复呢？依靠位置 3。

1. 对于 i 是素数的情况，这个和下一个素数 prime[j + 1] 继续标记肯定不会重复;
2. 对于 i 是合数的情况，如果这个合数分解质因数后:
   1. 最小的质因数等于 prime[j], 则若继续与下一个素数 prime[j + 1]相乘标记合数，就违反了不重复的约定-----因为对于由 i * prime[j + 1] 标记的合数，显然有更小的素数 prime[j] 去做乘积来标记。所以这种情况就应该停止迭代。
   2. 最小质因数大于 prime[j]，则就可以继续与下一个素数相乘继续标记，下一轮迭代不会出现重复标记的情况。