1007. 素数对猜想

 1 /*
 2     1007. 素数对猜想
 3 */
 4 
 5 #include <stdio.h>
 6 #include <string.h>
 7 #include <math.h>
 8 #include <stdlib.h>
 9 #include <time.h>
10 
11 #define maxn 100001
12 int p[maxn] = {0};                // 存储素数表 
13 
14 // 求素数表 
15 void findPrime(int N) {
16     int i, j;
17     for(i=2; i<=N; ++i) {
18         if(!p[i]) {                // 为素数 
19             // 标记倍数为非素数 
20             for(j=i+i; j<=N; j+=i) {
21                 p[j] = 1;
22             } 
23         }
24     }
25 }
26 
27 int main() {
28     int N, i, cnt=0;
29     scanf("%d", &N);
30     findPrime(N);                // 求素数表 
31     for(i=2; i<N-1; ++i) {
32         if(!p[i] && !p[i+2]) {    // 验证是否为素数对 
33             cnt++;
34         }
35     }
36     printf("%d", cnt);
37 
38     return 0;
39 }