收藏
关注如果一个质数，在质数列表中的编号也是质数，那么就称之为质数中的质数。例如：3 5分别是排第2和第3的质数，所以他们是质数中的质数。现在给出一个数N，求>=N的最小的质数中的质数是多少（可以考虑用质数筛法来做）。
Input
输入一个数N(N <= 10^6)
Output
输出>=N的最小的质数中的质数。
Input示例
20
Output示例
31
法一、筛出质数后再筛质数中的质数
#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=;i<N;i++)
{
if(!v[i]) prime[++cnt]=i;
for(int j=;j<=cnt;j++)
{
if(prime[j]*i>N-) break;
v[i*prime[j]]=true;
if(i%prime[j]==) break;
}
}
for(int i=;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 ;
}
}
法二、
#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=;i<N;i++)
{
if(!v[i]) prime[++cnt]=i;
for(int j=;j<=cnt;j++)
{
if(prime[j]*i>N-) break;
v[i*prime[j]]=true;
if(i%prime[j]==) break;
}
}
scanf("%d",&n);
int pos;
pos = upper_bound( prime, prime + cnt, n - ) - prime;
//第一个大于等于n的质数的编号，也就是自pos以后的质数，都满足题目>=n的要求
pos = upper_bound( prime, prime + cnt, pos- ) - prime;
//所以要找>=pos的质数，最小的在哪一个位置
printf( "%d\n", prime[prime[pos]] );
}