线性筛

userId_undefined

蒟蒻

2024-07-23 10:50:57

发布于：北京

15阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
int p[100000010];
bool v[100000009];
int lp=0;//素数个数
void d(int n){
    v[0]=v[1]=true;//v[0]&v[1]单独处理
    
    for(int i=2;i<=n;i++){//从2开始
if(!v[i]){p[++lp]=i;}//找到素数，存入素数数组
    for(int j=1;j<=lp;j++){//筛去当前i与素数数组元素的积
          if(1ll*i*p[j]>n)break;//超出筛选范围
          v[i*p[j]]=true;//后面数字都能被i更大的数字筛掉
          if(i%p[j]==0){break;}  
        }
    }
cout<<lp<<endl;}
int main(){
    int n;
    cin>>n;
   d(n);
   
return 0;}
userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论