鸭蛋仙人的博客

欧拉筛（线性筛）

问题描述：给定正整数n，求1到n之间的所有素数。

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
const int N = 1e6+10;
bool not_prime[N];
int cnt=0;
vector<int> primes;
void pre(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!not_prime[i]) primes.push_back(i);
        for(auto pri:primes) //一直遍历，直到找到i的最小质因数为止
        {
            if(1ll*i*pri>n) break;  
            not_prime[pri*i]=true;   //若pri不是最小质因数，则pri*i一定是一个没被筛的合数，pri是pri*i的最小质因数
            if(i%pri==0) break;   //如果i能被pri整除，则pri是i的最小质因数,primes中比pri更大的pri不可用于筛质数，因为它们的最小质因数一定大于pri
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    pre(n);
    cout<<primes.size();
    
}