51nod 1181 质数中的质数

#include<cstdio>
#include<algorithm>
#define N 1001001
using namespace std;
int n,prime[N],cnt;
bool v[N],g[N];
int main()
{
    for(int i=2;i<N;i++)
    {
        if(!v[i]) prime[++cnt]=i;
        for(int j=1;j<=cnt;j++)
        {
            if(prime[j]*i>N-1) break;
            v[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
    for(int i=1;i<=cnt;i++)
     g[prime[prime[i]]]=true;
    scanf("%d",&n);
    for(int i=n;i<N;i++)
     if(g[i]) 
     {
         printf("%d",i);
         return 0;
     }
}

#include<cstdio>
#include<algorithm>
#define N 1001001
using namespace std;
int n,prime[N],cnt;
bool v[N],g[N];
int main()
{
    for(int i=2;i<N;i++)
    {
        if(!v[i]) prime[++cnt]=i;
        for(int j=1;j<=cnt;j++)
        {
            if(prime[j]*i>N-1) break;
            v[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
    scanf("%d",&n);
    int pos;
    pos = upper_bound( prime, prime + cnt, n - 1 ) - prime;
    //第一个大于等于n的质数的编号，也就是自pos以后的质数，都满足题目>=n的要求 
    pos = upper_bound( prime, prime + cnt, pos-1 ) - prime;
    //所以要找>=pos的质数，最小的在哪一个位置 
    printf( "%d\n", prime[prime[pos]] );
}