首页 > 代码库 > 1007. 素数对猜想 (20)

1007. 素数对猜想 (20)

2024-09-06 05:17:12   214人阅读

让我们定义 dn 为：dn = pn+1 - pn，其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

现给定任意正整数N (< 105)，请计算不超过N的满足猜想的素数对的个数。

输入格式：每个测试输入包含1个测试用例，给出正整数N。

输出格式：每个测试用例的输出占一行，不超过N的满足猜想的素数对的个数。

输入样例：

20

输出样例：

4

 1 #include "stdio.h"
 2 #include "math.h"
 3 
 4 
 5 //判断是不是素数,
 6 int isPreme(int num)
 7 {
 8     int i;
 9     int flag = 1;
10     if (num <= 1)
11         return 0;
12     if (num == 2)
13         return 1;
14     for(i = 2; i < sqrt(num)+1; i++)
15     {
16         if(num % i == 0)
17         {
18             flag = 0;
19             break;
20         }
21     }
22     return flag;  //flag 1 是素数，flag = 0不是素数
23 }
24 
25 int main(int argc, char const *argv[])
26 {
27     int i,num=0;    
28     while(scanf("%d",&num) != EOF)
29     {
30         int preme1 = 2, preme2 = 2;
31         int count = 0;
32         if (num <= 0 || num >= 100000)
33         {
34             printf("error\n");
35             exit(0);
36         }
37         for (i = 3; i <= num; ++i)  //从3开始计算素数
38         {
39             if(isPreme(i))
40             {
41                 if(i - preme2 == 2)
42                     count++;
43                 preme1 = preme2;
44                 preme2 = i;
45             }
46         }
47         printf("%d\n", count);
48     }
49     return 0;
50 }

 

1007. 素数对猜想 (20)


联系
我们