PAT1007 素数对猜想

题目

让我们定义$d_​n$为：$d_n=p_{n+1}-p_n$，其中$p_i$是第$i$个素数。显然有$d_1=1$，且对于$n>1$有$d_n$是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

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

输入格式

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

输出格式

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

输入样例

20

输出样例

4

思路

水题，判断是否素数，记录上次结果，差为2，计数+1。

代码

//pat1007
#include <iostream>
using namespace std;

bool isPrime(int num)
{
    if(num < 2)
    {
        return false;
    }
    for(int i = 2; i * i <= num; i++)
    {
        if(num % i == 0)
            return false;
    }
    return true;
}

int main(int argc, char const *argv[])
{
    int primeNum, primeS = 2, primeE = 2, count = 0;
    cin >> primeNum;
    for(int i = 2 ; i <= primeNum; i++)
    {
        if(isPrime(i))
        {
            primeE = i;
            if(primeE - primeS == 2)
            {
                count++;
            }
            primeS = primeE;
        }
    }
    cout << count;

    return 0;
}