埃氏筛法是一种由希腊数学家埃拉托斯特尼所提出的一种筛选质数(又称作素数)的算法。
欧拉筛法相比于埃氏筛法，其效率更高。
这里对二者进行思路分析与代码解释。

已知事实

任何一个合数都能够分解成几个质数相乘的形式

埃氏筛法

代码部分

#include <bits/stdc++.h>
#define MAXN 10005
using namespace std;

int main()
{
    bool is_prime[MAXN];       //记录is_prime[i]是否为质数
    int prime[MAXN], cnt = 0;  //prime为已记录的质数列表,cnt为已得到的质数个数
    int n = 10000;             //从区间(0,n]中筛选质数
    for (int i = 0; i <= n; ++i) is_prime[i] = true;//初始化全部质数，后面排除
    is_prime[0] = false;
    is_prime[1] = false; // 0,1不是质数

    for (int i = 2; i <= n; i++)
    {
        if (is_prime[i])
        {
            cnt++;          //质数个数+1
            prime[cnt] = i; //将质数加入数组prime
        }
        /*重点在这*/
        for (int j = i * 2; j <= n; j += i) //将i的倍数(j)依次在数组中标记
        {
            is_prime[j] = false;
        }
    }

    /*输出指定质数*/
    int order = 1;
    printf("No.%d==>%d\n", order, prime[order]);

    /*输出所有质数*/
    for (int i = 1; i <= cnt; i++)
    {
        printf("%d ", prime[i]);
    }
    return 0;
}

思路解析

在埃氏筛法中，找到一个质数（从2开始），把这个质数的所有倍数标记出来
例：对于质数2，我们将二的倍数4,6,8,10……标记出来
相比于暴力筛选，这种方法更为快速

代码优化

1.排除部分重复

在代码for(int j=i*2;j<=n;j+=i)中，由于在前面的循环里从2*i到(i-1)*i已经计算过，所以我们可以直接使j从i*i开始循环
具体解释：

  • j=i当前*2时，i当前*2在前面已经计算出来过，具体在什么时候呢？在i过去=2, j过去遍历到等于i当前的时候。*3，*4……以此类推，都已经在前面计算过。
  • 直到j=i当前*(i-1)时，i当前*(i-1)在前面已经计算出来过，具体在i过去=(i-1), j过去遍历到等于i当前的时候。

优化片段

for (int j = i * i; j <= n; j += i)
{
    is_prime[j] = false;
}

2.筛至平方根

要找到n之前的所有质数，我们筛选到 $\sqrt n$ 即可
优化片段

for (int i = 2; i*i <= n; i++) //此处i*i<=n相当于i<=sqrt(n)
{
    if (is_prime[i])
    {
        cnt++;          
        prime[cnt] = i;
    }
    for (int j = i * i; j <= n; j += i)
    {
        is_prime[j] = false;
    }
}

欧拉筛法

埃氏筛法即使进行优化，也会将一个合数标记多次，欧拉筛法提供了一个只需要将每个合数标记一次的思路

引自网络：欧拉筛法又叫线性筛法，因为其时间复杂度是线性的，即O(n)

代码部分

#include <bits/stdc++.h>
#define MAXN 10005
using namespace std;

int main()
{
    bool is_prime[MAXN];       //记录is_prime[i]是否为质数
    int prime[MAXN], cnt = 0;  //prime为已记录的质数列表,cnt为已得到的质数个数
    int n = 10000;             //从区间(0,n]中筛选质数
    memset(is_prime, true, sizeof(is_prime));//初始化全是质数，后面排除
    is_prime[0] = false;
    is_prime[1] = false; // 0,1不是质数

    for (int i = 2; i <= n; i++)
    {
        if (is_prime[i])
        {
            cnt++;          //质数个数+1
            prime[cnt] = i; //将质数加入数组prime
        }

        /*将i与每个已得到的质数(prime[j])相乘得到的合数在数组中标明*/
        /*如果i与某个已得到的质数乘积超过所求范围(n)，则结束*/
        for (int j = 1; j <= cnt && i * prime[j] <= n; j++)
        {
            is_prime[i * prime[j]] = false;
            if (i % prime[j] == 0) /*算法关键点，后面单独解释*/
                break;
        }
    }

    /*输出指定质数*/
    int order = 1;
    printf("No.%d==>%d\n", order, prime[order]);

    /*输出所有质数*/
    for (int i = 1; i <= cnt; i++)
    {
        printf("%d ", prime[i]);
    }
    return 0;
}

思路解析

从1开始，将每一个数与已得到的质数相乘并作为合数标记在数组is_prime中

if (i % prime[j] == 0) break;的解释

易知，当i % prime[j] == 0时，prime[j]是i的最小质因数

此时若没有break，则后面j的循环里筛掉的一个数(设为x)有：x = i * prime[k]（这里k>j）

因此x的因数中中必定含有素因数prime[j]，而除prime[j]之后得到的x/prime[j]必定大于i（∵primes[k]/primes[j] > 1，∴i*(primes[k]/primes[j]) > i）
所以这里的x会在后面的i的循环中被更大的i（即x/prime[j]）筛掉
所以当i % prime[j] == 0，要break，避免重复筛一个数。这也是它比埃氏筛法快的核心。