基准时间限制:1 秒 空间限制:131072 KB
如果一个质数,在质数列表中的编号也是质数,那么就称之为质数中的质数。例如:3 5分别是排第2和第3的质数,所以他们是质数中的质数。现在给出一个数N,求>=N的最小的质数中的质数是多少(可以考虑用质数筛法来做)。
Input
输入一个数N(N <= 10^6)
Output
输出>=N的最小的质数中的质数。
Input示例
20
Output示例
31
#include <cstdlib> #include <map> #include <cstring> #include <iostream> int main() { int *is_prime; is_prime= (int *) malloc(sizeof(int) *10010000); is_prime[0]= is_prime[1]= 1; for(int i=2; i<10010000; i++) { if(!is_prime[i]) for(int j=i+i; j<10010000; j+= i) { is_prime[j]= 1; } } std::map<int, int> m; int cnt=1; for(int i=1; i<= 10010000; i++) { if(!is_prime[i]) { m[i]= cnt++; } } int n; while(std::cin>> n) { int rec; for(int i=n; ; i++) { if(!is_prime[i] && !is_prime[m[i]]) { rec= i; break; } } std::cout<< rec<<' '; } free(is_prime); is_prime=NULL; return 0; }