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

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 const int N = 1000001;
 8 int prime[N+1];
 9 void getPrime(){
10     memset(prime, 0, sizeof(prime));
11     for(int i = 2;i <= N; i++){
12         if(!prime[i])
13             prime[ ++prime[0] ] = i;
14         for(int j = 1; j <= prime[0] && prime[j] <= N / i; j++){
15             prime[ prime[j] * i ] = 1;
16             if(i % prime[j] == 0) break;
17         }
18     }
19 }
20 int main(){
21     getPrime();
22     int i, n, f;
23     scanf("%d", &n);
24     f = upper_bound(prime+1, prime + 1 + prime[0], n-1) - prime;
25     f = upper_bound(prime+1, prime + 1 + prime[0], f-1) - prime;
26     printf("%d
", prime[prime[f]]);
27     return 0;
28 }
View Code