素数筛

埃筛

#include <cstdio>
#include <iostream>
#include <bitset>
#include <ctime>
using namespace std;

bitset<10000010> pri;
int primes[10000100],pp=0;

int main(){
    double s=clock();
    for(int i=2;i<10000010;i++){
        if(!pri[i]) primes[pp++]=i;
        for(int j=0;i*primes[j]<10000000;j++){
            pri[i*primes[j]]=1;
            if(i%primes[j]==0){
                break;
            }
        }
    }
    double e=clock();
    printf("TIME:%.0lfms\n",(e-s));
    int x;
    while(scanf("%d",&x)!=EOF){
        cout<<primes[x]<<endl;
    }
    return 0;
}

欧拉筛

#include <cstdio>
#include <iostream>
#include <bitset>
#include <ctime>
using namespace std;

bitset<10000010> pri;
int primes[10000100],pp=0;

int main(){
    double s=clock();
    for(int i=2;i<10000010;i++){
        if(!pri[i]) primes[pp++]=i;
        for(int j=0;i*primes[j]<10000000;j++){
            pri[i*primes[j]]=1;
            if(i%primes[j]==0){
                break;
            }
        }
    }
    double e=clock();
    printf("TIME:%.0lfms\n",(e-s));
    int x;
    while(scanf("%d",&x)!=EOF){
        cout<<primes[x]<<endl;
    }
    return 0;
}