codevs 2530大质数

链接：http://codevs.cn/problem/1530/

解题思路：
这个题最关键的剪枝还是 因子小于平方根，但不是像原来那样用。
逆转思维，与其说判断哪些是质数，不如说判断哪些不是质数，更简单，更效率。
所有的合数都有一个共同的特点，就是能被拆成质因子。
那么已经出现的质因子，迟早有一次会成为一个合数的因子。
那么直接拿要判断的数挨个被质数除一遍，就可以直接判断是不是合数了。
写到这，前三个点就过了，至于最后一个100000，就是开头提到的剪枝。
不管怎样，一个合数里面的质因子一定也小于它的平方根
所以提前判断一下，试到第几个合数停止，即可效率大大提高。

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int n,ans,prime[100001],ph;//ph表示当前要搜的是第几个质数。 

int divide(double x){//判断试到第几个素数为止 
    int temp=(int)x;
    for (int i=1;i<ph;i++){
        if (prime[i]>temp) return i-1;
    }
}

int main(){
    cin>>n;
    prime[1]=2;
    prime[2]=3;
    ph=2;
    bool check;
    int temp,test;
    while(ph<n){//递归 
        temp=prime[ph];
        ph++;
        while (1){
            temp++;
            test=divide(sqrt(temp));
            for (int i=1;i<=test;i++) {
                if (temp % prime[i]==0) {check=true;break;}
            }//挨个除一遍 
            if (check) {check=false;continue;}
            prime[ph]=temp;
            break;
        }
    }
    cout<<prime[n];
}