PAT-B 真题- 1007. 素数对猜想

题干如下:

让我们定义 d_n 为：d_n = p_n+1 - p_n，其中 p_i 是第i个素数。显然有 d₁=1 且对于n>1有 d_n 是偶数。"素数对猜想"认为"存在无穷多对相邻且差为2的素数"。

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

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

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

输入样例：

20

输出样例：

4

这里我们的解题思路为，算出所有小于N的素数，并在每计算出一个新的素数时，比较与前一个素数相差是否为2。

在计算素数时，我们边计算素数，边把这些素数存储起来，这样只要让新的数字与之前计算过的所有素数相除，如果无法整除，我们就判定它是个素数。

下面的代码我是用C++标准模板库里面的vector容器写的，仅供参考。当然你也可以用数组去写。

#include <cstdio>
#include <vector>
using namespace std;
vector<int> prime;

bool isPrime(int num){
  for(vector<int>::iterator it = prime.begin(); it != prime.end(); it++){
    if(num % (*it) == 0){
      return 0;
    }
  }
  return 1;
}

int main(void){
  int n, sum = 2, i = 0;
  vector<int>::iterator it = prime.begin();
  scanf("%d", &n);
  if(n==2){
    printf("0");
    return 0;
  }
  while(sum <= n){
    if(isPrime(sum)){
      prime.push_back(sum);
      if((sum != 2) && (sum - *(it - 1)) == 2)
        i++;
      it = prime.end();
    }
    sum++;
  }
  printf("%d",i+1);
  return 0;
}

完美通过。