Prime Number

埃氏筛法：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10000000;
int prime[maxn];
bool IsPrime[maxn] = {0};//0代表都是素数
void Find_Prime(){
    IsPrime[1] = 1;//1不是素数
    int pNum = 1;
    for(int i = 2; i <= maxn; i++){
        if(!IsPrime[i])
            prime[pNum++] = i;
        for(int j = i * i; j <= maxn; j += i){
            IsPrime[j] = true;
        }
    }
}
int main(){
    int k;
    Find_Prime();
    while(~scanf("%d", &k)){
        printf("%d\n", prime[k]);
    }
    return 0;
}

欧拉筛法

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10000000;
int prime[maxn];
bool IsPrime[maxn];//0代表都是素数
void Find_Prime(){
    IsPrime[1] = 1;//1不是素数
    int pNum = 0;
    for(int i = 2; i <= maxn; i++){
        if(!IsPrime[i]){
            prime[pNum++] = i;   
        }
        for(int j = 0; j < pNum && i * prime[j] <= maxn; j++){
            IsPrime[i * prime[j]] = 1;
            if(i % prime[j] == 0){
                break;
            }
        }
    }
}
int main(){
    int k;
    Find_Prime();
    while(~scanf("%d", &k)){
        printf("%d\n", prime[k - 1]);
    }
    return 0;
}