欧拉筛(线性筛)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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();

}


http://example.com/2025/05/25/算法/数学模版/
作者
bradin
发布于
2025年5月25日
许可协议