nyoj 26-孪生素数问题(打表)

26-孪生素数问题

内存限制:64MB 时间限制:3000ms Special Judge: No
accepted:10 submit:43

题目描述:

写一个程序，找出给出素数范围内的所有孪生素数的组数。一般来说，孪生素数就是指两个素数距离为2，近的不能再近的相邻素数。有些童鞋一看到题就开始写程序，不仔细看题，咱们为了遏制一下读题不认真仔细的童鞋，规定，两个素数相邻为1的也成为孪生素数。

输入描述:

第一行给出N(0<N<100)表示测试数据组数。
接下来组测试数据给出m，表示找出m之前的所有孪生素数。
(0<m<1000000)

输出描述:

每组测试数据输出占一行，该行为m范围内所有孪生素数组数。

样例输入:

1
14

样例输出:

4

分析：
　　①、因为每次测试都有多组数据且都在1e6以内，考虑到数据量不是很大，所以我们可以先将每一个点n的（0， n）区域中的孪生素数计算出来，放在一个数组中
　　②、当需要的时候，可以直接通过数组的对应关系确定该点的孪生素数个数
　　③、说明：距离只差为1的素数其实只有一对（即就是2 、 3）

步骤：
　　①、打表
　　②、通过表输出孪生素数个数

核心代码：

 1 for(int i = 4; i < MAXN; ++ i)
 2 {
 3     if(is_pritme(i))
 4     {
 5         if(i - a == 2) A[i] = A[i-1] + 1;
 6         else A[i] = A[i-1];
 7         a = i;
 8     }
 9     else
10     {
11         A[i] = A[i-1];
12     }
13 }

C/C++代码实现（AC）：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <queue>
 7 #include <set>
 8 #include <map>
 9 #include <stack>
10 
11 using namespace std;
12 const int MAXN = 1e6 + 10;
13 int A[MAXN] = {0, 0, 0, 1};
14 
15 bool is_prime(int n)
16 {
17     int temp = sqrt(n);
18     for(int i = 2; i <= temp; ++ i)
19         if(n%i == 0) return false;
20     return true;
21 }
22 
23 void cal_excel()
24 {
25     int a = 3;
26     for(int i = 4; i < MAXN; ++ i)
27     {
28         if(is_prime(i))
29         {
30             if(i - a == 2) A[i] = A[i-1] + 1;
31             else A[i] = A[i-1];
32             a = i;
33         }
34         else
35         {
36             A[i] = A[i-1];
37         }
38     }
39     return ;
40 }
41 
42 int main ()
43 {
44     cal_excel();
45     int t;
46     scanf("%d", &t);
47     while(t --)
48     {
49         int n;
50         scanf("%d", &n);
51         printf("%d
", A[n]);
52     }
53     return 0;
54 }