51nod 1181 质数中的质数（质数筛法）

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

题目来源： Sgu

基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题

关注

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

Input

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

Output

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

Input示例

Output示例

31

题解：先对自然数组用质数筛法筛一次，再对质数数组筛一次，然后用二分法找到第一个不小于N的值。

AC代码

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 const int maxn=1e6+10;
 5 int prime[maxn];
 6 int a[maxn];
 7 bool valid[maxn];
 8 int tot;
 9 void get_prime(int a[],int sum)
10 {
11     tot=0;
12     for(int i=2;i<=sum;i++)
13         valid[i]=true;
14     for(int i=2;i<=sum;i++)
15     {
16         if(sum/i<i)
17             break;
18         if(valid[i])
19         {
20             for(int j=i*i;j<sum;j+=i)
21                 valid[j]=false;
22         }
23     }
24     for(int i=2;i<=sum;i++)
25     if(valid[i])
26         prime[++tot]=a[i];
27 }
28 int main()
29 {
30     int n;
31     cin>>n;
32     for(int i=0;i<=1000005;i++)
33         a[i]=i;
34     get_prime(a,1000005);
35     get_prime(prime,tot);
36     int ans=lower_bound(prime,prime+tot,n)-prime;
37     cout<<prime[ans]<<endl;
38     return 0;
39 }

View Code