1181 . 质数中的质数（质数筛法）

时间：2014-02-23 10:38:06 收藏：0 阅读：248

1181 . 质数中的质数（质数筛法）

题目来源： Sgu

时间限制：1 秒空间限制：65536 KB 分值: 0

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

Input

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

Output

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

Input 示例

Output 示例

熟悉下质数筛选的做法：

#include <stdio.h>
#define N 1000160
typedef __int64 LI;
bool f[N+1]={false};
int prime[N+1];
int main(){
	int n;
	scanf("%d",&n);
	LI cnt=0,i,j;
	f[1]=true;
	f[2]=false;
	for(i=2;i<=N;i++){
		if(!f[i]){
			cnt++;
			if(!f[cnt]&&i>=n){
				printf("%d\n",i);
				break;
			}
			for(j=i*i;j<=N;j+=i)
				f[j]=true;
		}
	}

    return 0;
}

原文：http://blog.csdn.net/starcuan/article/details/19702003