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

发布于 2017-12-06  16 次阅读


题目描述

如果一个质数,在质数列表中的编号也是质数,那么就称之为质数中的质数。例如: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;
}

 

]]>


「墨泼三千烟火,许你一世迷离」