埃氏筛法

userId_undefined

忘川秋库

7月全勤卷王小有名气集训营话痨荣耀黄金题解仙人传道者

2025-07-25 19:50:34

发布于：浙江

6阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
const long long N=100000010;
bool isP[N];//i这个数是否是一个素数，true即是，false即否
void sieve(long long n){
    memset(isP,1,sizeof(isP));
    isP[0]=isP[1]=false;//6.7两行都为初始化操作
    for(long long i=2;i<=sqrt(n);i++){
        if(isP[i]){
            for(int j=i*i;j<=n;j+=i){//处理i的倍数
                isP[j]=false;
            }
        }
    }
}int main(){
    long long n;
    cin>>n;
    sieve(n);
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(isP[i])cnt++;
    }cout<<cnt;
}//时间复杂度O(sqrt(n)logn)
userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论