• 适用场景：求2~N范围内的素数
• 优点：线性筛，复杂度为O(n)。与埃氏筛相比，不会对已经被标记过的合数再进行重复标记，故效率更高。欧拉筛将合数分解为 (最小质因数 * 一个合数) 的形式，通过最小质因数来判断当前合数是否已经被标记过。
• 流程：我们知道当一个数为素数的时候，它的倍数肯定不是素数。所以我们可以从2开始通过乘积筛掉所有的合数。
• 避免重复筛除原理：任何合数都能表示成多个素数的积。所以，任何的合数肯定有一个最小质因子。我们通过这个最小质因子就可以判断什么时候不用继续筛下去了。
  • 比如对于77,它分解质因数是7*11，那么筛掉所有小于等于7的质数*77，筛掉2*77、3*77、5*77、7*77
• 代码

#include <cstdio>
#include <cstring>
const int maxn=1000;    //表长
int prime[maxn],pNum=0;    //记录素数
bool p[maxn];
int N;  //求N以内的素数

void f(int n){
    for(int i=2;i<=n;i++){
        if(!p[i])   //如果没有被筛掉，说明它是素数
            prime[pNum++]=i;
        for(int j=0;j<pNum;j++){  //从已找出的素数中从小到大遍历，直到i的最小质因数
            if(i*prime[j]>n)
                break;
            p[i*prime[j]]=true;
            if(i%prime[j]==0)  //说明prime[j]是i的最小质因数（质数顺序列表中第一个发现的可整除的质数）
                break;
        }
    }
}
int main(){
    memset(p,0,sizeof(p));
    scanf("%d",&N);
    f(N);
    for(int i=0;i<pNum;i++){
        printf("%d ",prime[i]);
    }
    return 0;
}

• 原理：见百度。