Prime

埃式篩














void Sieve(int N){
    vector<bool> isprime(N,true);
    for(int i=2;i<N;i++){
        if(isprime[i]){
            for(int j=i*i;j<N;j+=i){
                isprime[j]=false;
            }
        }
    }
    for(int i=2;i<N;i++){
        if(isprime[i]) cout << i << ' ';
    }
}

線性篩














void Linear_Sieve(int N){
    vector<int> prime;
    vector<bool> isprime(N,true);
    for(int i=2;i<N;i++){
        if(isprime[i]) prime.pb(i);
        for(auto j:prime){
            if(i*j>=N) break;
            isprime[i*j]=false;
            if(i%j==0) break;
        }
    }
    for(auto i:prime) cout << i << ' ';
}
Select a repo