51nod 1181_质数中的质数_筛素数

lzusa 发布于 2017-12-06 1062 次阅读

题目描述

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

#include 
#define N 1000005
bool notprime[N];
int prime[N], tot, f[N];
int work()
{
    for (int i = 2; i <= N; i++)
    {
        if (!notprime[i])
        {
            prime[++tot] = i;
            f[i] = tot;
        }
        for (int j = 1; j <= tot && i * prime[j] <= N; j++)
        {
            notprime[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
    return 0;
}
int main()
{
    int n;
    scanf("%d", &n);
    work();
    for (int i = n; ; i++)
    {
        if (!notprime[i] && !notprime[f[i]])
        {
            printf("%d\n", i);
            break;
        }
    }
    return 0;
}

 

]]>