【Prime Number】 两种方式

/* 方法一：枚举（不需要重复求子问题，稍有优化）
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> kList;    //需求列表
vector<int> prime;    //maxK个素数
bool isPrime(int n){
    bool flag = true;
    if(n<2)
        flag = false;
    int bound = sqrt(n);
    for(int i=2; i<=bound; i++){
        if(n%i==0)
            flag = false;
    }
    return flag;
}
int main(){
    int k;
    while(cin>>k){
        kList.push_back(k);
    }
    sort(kList.begin(),kList.end());    //找到最大的 k ,避免重复计算子问题
    int maxK = kList[kList.size()-1];
    for(int i=2; prime.size()<=maxK; i++){
        if(isPrime(i)){
            prime.push_back(i);
        }
    }
    for(int r=0;r<kList.size();r++){
        //         第k个素数在prime数组里的index=k-1
        cout<<prime[kList[r]-1]<<endl;
    }
    return 0;
}
*/

/* 方法二：倍数标记法 */
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxN = 10000000;
vector<int> prime;
bool isPrime[maxN];
void init(){
    fill(isPrime,isPrime+maxN,true);    //将isPrime[]初始化为true
    isPrime[0] = false;
    isPrime[1] = false;
    for(int i=2; i<maxN; i++){    //在遍历到i之前，如果没有i的因子把i标记为false，则i一定是prime
        if(isPrime[i]){
            prime.push_back(i);
        }
        for(int j=i*i ; j<maxN; j=j+i){    //i的倍数标记为not prime
            isPrime[j] = false;            //从 i*i 开始，为了减少重复标记的工作量
        }
    }
}
int main(){
    init();
    int k;
    while(cin>>k){
        cout<<prime[k-1]<<endl;
    }
    return 0;
}