文章来源地址https://www.toymoban.com/news/detail-406402.html
线性筛O（n）而埃氏筛进行筛时会重复筛，线性筛不会出现这个问题
线性筛：对于某个合数使用其最小质因子筛去
st[primes[j] * i] = true; 因为这句话只会被执行一次，所以复杂度O(fn)
文章来源：https://www.toymoban.com/news/detail-406402.html
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
bool st[N];
int cnt,n,p[N];
void get_primes(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i]) p[cnt++]=i;
for(int j=0;p[j]*i<=n;j++)
{
st[i*p[j]]=true;
if(i%p[j]==0) break;
}
}
}
int main()
{
cin>>n;
get_primes(n);
cout<<cnt;
}到了这里，关于线性筛法 O(n)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[Go版]算法通关村第十三关黄金——数字数学问题之数论问题（最大公约数、素数、埃氏筛、丑数）](https://imgs.yssmx.com/Uploads/2024/02/668230-1.png)
