题目来源： 

基准时间限制：1 秒 空间限制：131072 KB 分值: 0 

 收藏

 关注

如果一个质数，在质数列表中的编号也是质数，那么就称之为质数中的质数。例如：3 5分别是排第2和第3的质数，所以他们是质数中的质数。现在给出一个数N，求>=N的最小的质数中的质数是多少（可以考虑用质数筛法来做）。

 

Input

输入一个数N(N <= 10^6)

Output

输出>=N的最小的质数中的质数。

Input示例

20

Output示例

31 法一、筛出质数后再筛质数中的质数

#include
       
        #include
        
         #define N 1001001using namespace std;int n,prime[N],cnt;bool v[N],g[N];int main(){    for(int i=2;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
         
        
       

法二、

#include
       
        #include
        
         #define N 1001001using namespace std;int n,prime[N],cnt;bool v[N],g[N];int main(){    for(int i=2;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]] );}