526互联

1007 素数对猜想（C++）

发布时间 2023-04-27 21:52:54作者: 轻挼草色

一、问题描述：

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

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

输入格式:

输入在一行给出正整数N。

输出格式:

在一行中输出不超过N的满足猜想的素数对的个数。

二、设计思路：

  1. 输入整数，计数器count=0；
  2. 建立一个函数判断是否为素数，再建一个函数找出该数所有素数；
  3. 将相邻素数相减差为2，count加1；
  4. 输出count。

三、代码实现：

判断素数时要用根号，要不最后一个测试点过不了，会运行超时。

 1 #include <iostream>
 2 #include <cmath>
 3 using namespace std;
 4 int Isprime(int m)//判断是否为素数
 5 {
 6     int flag = 1;
 7     for (int i = 2; i <= (int)sqrt(m); i++)
 8     {
 9         if (m % i == 0)
10             flag = 0;
11     }
12     return flag;
13 }
14 int findprime(int n, int a[])//找出所有素数，存入数组中
15 {
16     int j=0;
17     for (int i = 2; i <= n; i++)
18     {
19         if (Isprime(i))
20         {
21             a[j] = i;
22             j++;
23         }
24     }
25     return j;//返回素数个数
26 }
27 int main()
28 {
29     int n;
30     int count = 0;
31     int length;
32     int a[100000] = { 0 };
33     cin >> n;
34     length=findprime(n, a);
35     for (int i = 1; i <= length; i++)
36     {
37         if (a[i] - a[i - 1] == 2)
38         {
39             count++;
40         }
41     }
42     cout << count << endl;
43     return 0;
44 }