链接：http://codevs.cn/problem/1530/
解题思路：
这个题最关键的剪枝还是 因子小于平方根，但不是像原来那样用。
逆转思维，与其说判断哪些是质数，不如说判断哪些不是质数，更简单，更效率。
所有的合数都有一个共同的特点，就是能被拆成质因子。
那么已经出现的质因子，迟早有一次会成为一个合数的因子。
那么直接拿要判断的数挨个被质数除一遍，就可以直接判断是不是合数了。
写到这，前三个点就过了，至于最后一个100000，就是开头提到的剪枝。
不管怎样，一个合数里面的质因子一定也小于它的平方根
所以提前判断一下，试到第几个合数停止，即可效率大大提高。
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int n,ans,prime[],ph;//ph表示当前要搜的是第几个质数。 int divide(double x){//判断试到第几个素数为止
int temp=(int)x;
for (int i=;i<ph;i++){
if (prime[i]>temp) return i-;
}
} int main(){
cin>>n;
prime[]=;
prime[]=;
ph=;
bool check;
int temp,test;
while(ph<n){//递归
temp=prime[ph];
ph++;
while (){
temp++;
test=divide(sqrt(temp));
for (int i=;i<=test;i++) {
if (temp % prime[i]==) {check=true;break;}
}//挨个除一遍
if (check) {check=false;continue;}
prime[ph]=temp;
break;
}
}
cout<<prime[n];
}