如何快速查找素数

/*
  如果要迁移使用其中的函数，需要修改一些常量。
*/

#include<iostream>
#include<vector>
#include<string>
#include<math.h>

using namespace std;

//朴素的暴力检查法
int getNthPrimerSimple(int n){
    for(int i = 2;true;i++ ){
        bool isp = true;
        for(int j = 2;j <= sqrt(i) && isp;j++ ){
            if(i%j == 0){
                isp = false;
            }
        }
        n -= isp;
        if(n == 0) return i;
    }
    return -1;
}

//只检查质因数法
int getNthPrimer(int n){
    vector<int> primes;
    for(int i = 2;primes.size() < n;i++ ){
        int idx = 0;
        for(;idx < primes.size();idx++ ){
            if(i % primes[idx] == 0) break;
        }
        if(idx == primes.size()) primes.push_back(i);
        //cout << i;
    }
    return primes.back();
}

//埃氏筛法
int eratosthenes(int x){
    const int n = 150000;
    vector<bool> f(n);
    for(int num = 2;num < n/2;num++ ){
        if(f[num]) continue;
        for(int i = num+num;i < n;i += num) f[i] = true;
    }
    int idx = 1;
    while(x > 0 && idx < n-1){
        if(!f[++idx]) --x;
    }
    return idx;
}

//欧式筛法，O(n)解法，使用了prims素数数组来避免重复计数
int euler(int x){
    const int n = 2000000;
    vector<bool> f(n);
    vector<int> prims(n);
    for(int num = 2;num < n;num++ ){
        if(!f[num]) prims[++prims[0]] = num;
        for(int j = 1;j <= prims[0] && num*prims[j] < n;++j ){
            f[prims[j]*num] = true;
            if(num%prims[j] == 0) break;
        }
    }
//    cout <<"p-size:" << prims[0];
    return x>prims[0]?-1:prims[x];
}

int main(){
    int n;
    //cin >> n;
    //for(int i = 0;i < 10000;i++ ){//950s
    //    cout << getNthPrimer(i+1) << ":" << getNthPrimerSimple(i+1) << " ";
    //}

    //for(int i = 0;i < 10000;i++ )//66.6s
    //    cout << eratosthenes(i+1) << " ";

    //for(int i = 0;i < 10000;i++ )//68.5s
    //    cout << euler(i+1) << " ";
    euler(100000);
    cout << endl;
    return 0;
}