C++实现欧拉筛法

Euler筛法介绍

以筛出100以内（含100）的所有素数为例来说明一下欧拉筛法的原理。

和Eratosthenes筛法一样，Euler筛法也从2开始筛，但Eratosthenes筛法会把2的倍数一批全部筛掉，而Euler筛法用2筛时仅仅把2*2（即4）筛掉，而把其它偶数留到后面再筛掉，从而避免了一个偶数被多次筛除带来的性能开销，比如偶数6、8、10，在随后用3、4、5筛的时候会被筛掉。

Euler筛法引入了一个素数队列，从2开始没被筛掉的数会依次加进素数队列，当用3筛时，素数队列里有2和3两个素数，这时会筛掉3*2（即6）和3*3（即9）。

当用4筛时，4因为之前被2筛掉了，所以4不会加进素数队列，此时素数队列里依然只有2和3两个素数，这时会筛掉4*2（即8），但4*3（即12）并不在这时筛掉，这是因为4本身是素数2的倍数，即4*3里不能保证3是最小素因数。

当用5筛时，先把5加入素数队列，随后筛掉5*2（即10）、5*3（即15）和5*5（即25）。

当用6筛时，6因为之前被3筛掉了，所以此时素数队列里依然只有2、3、5，这时会筛掉6*2（即12），但因为判断出6是2的倍数，随后就不会用6进一步去筛掉6*3（即18）。

当用7筛时，先把7加入素数队列，随后依次筛掉7*2（即14）、7*3（即21）、7*5（即35）和7*7（即49）。

当用8筛时，8因为之前被4筛掉了，所以此时素数队列里依然只有2、3、5、7，这时会筛掉8*2（即16），但因为判断出8是2的倍数，随后就不会用8进一步去筛掉8*3（即24）。

当用9筛时，9因为之前被3筛掉了，所以此时素数队列里依然只有2、3、5、7，这时会筛掉9*2（即18）和9*3（即27），但因为判断出9是3的倍数，随后就不会用9进一步去筛掉9*5（即45）。

当用10筛时，10因为之前被5筛掉了，所有此时素数队列里依然是2、3、5、7，这时会筛掉10*2（即20），但因为10是2的倍数，随后不会用10去筛掉10*3（即30）。

当用11筛时，先把11加入素数队列，随后依次筛掉11*2（即22），11*3（即33），11*5（即55），11*7（即77）。11*11（即121）因为大于100而不在筛查范围。

用12筛，只会筛去12*2。

用13筛，13进素数队列，随后依次筛去13*2，13*3，13*5，13*7。13*11不在筛查范围。

用14、15、16筛，依次会筛去14*2、15*2和15*3、16*2。

用17筛，17进素数队列，随后依次筛去17*2、17*3、17*5。17*7不在筛查范围。

……

用49筛，会筛去49*2。49*3不在筛查范围。

用50筛，会筛去50*2。50*3不在筛查范围。

用51筛，不会筛去任何数，因为51*2>100。

随后用52、53、……、99、100筛的过程里，都不再会筛去任何数，而只有素数进素数队列的行为。

由上述过程可知，欧拉筛法的核心思路是：对于筛查范围内的任意一个合数m，只使用m中除m之外最大的因数把m筛去。例如，45=3*3*5，确保用15筛去45即可。更一般的情形，m=p1*p2*……*ps，其中p1、p2、……、ps均为素数且满足p1<=p2<=……<=ps，则确保用p2*……*ps筛去m即可。

Euler筛法核心思路及证明：

当此时取出的素数表中的素数（即枚举的最小质因子）整除于当前枚举的合数时，我们就停止循环素数表，开始枚举下一个合数。

证明如下：

设当前枚举的最小质因子prime[i]整除于合数n时，即我们要筛掉合数 n*prime[i] ；如果我们此时不退出，继续枚举下一个素数prime[i+1]，对于将要筛掉的合数 n*prime[i+1] 由于插入顺序从小到大，则 prime[i+1]>prime[i]。由于prime[i]整除于合数n，所以必然合数 n*prime[i+1] 还可以被分解为

显然，在上面的分解方式中，我们将要筛掉的合数分解为更小的质因子 prime[i] ，这不符合我们对于每一个数被唯一分解的要求，所以我们可在代码中加入一行判断整除关系的代码进行优化。

Euler筛法的C++程序实现

#include<bits/stdc++.h>
using namespace std;
bool IsPrime[100005];
int prime[50005];

int eulerSieve(int n) {
    int top = 1;
    memset(IsPrime, 1, sizeof(IsPrime));
    for (int i = 2; i <= n; i++) {
        if (IsPrime[i])
            prime[top] = i, top++;
        for (int j = 1; j < top; j++) {
            if (i * prime[j] > n)
                break;
            IsPrime[i * prime[j]] = 0;
            if (i % prime[j] == 0)
                break;
        }
    }
    return top;
}
int main()
{
    int n, num;
    cin>>n;
    num= eulerSieve(n);
    for(int i=1;i<=num;i++)
    {
        cout<<prime[i]<<" ";
    }
    return 0;
}