欢乐赛#40 T4 题解

因为求质数的循环可以将运算过程写成sqrt(n)，所以这里时间复杂度是O(nlgn)
然后重复判断即可，因此代码如下：

#include <iostream> 
#include <cmath> 
using namespace std;
bool isPrime(int num) { 
    if (num < 2) return false; 
    for (int i = 2; i <= sqrt(num); i++){
        if (num % i == 0) return false; 
    } 
    return true; 
} 
int findNthPrime(int n){//find+Nth+Prime!!!
    int count = 0;//第几个
    int num = 2;//从2开始检查 
    while(1){
        if(isPrime(num)){
            count++;
            if (count == n){
                return num;
            }
        }
        num++;
    }
}
int main() { 
    int n; 
    cin >> n; 
    cout << findNthPrime(n) << endl; 
    return 0; 
}