1007 素数对猜想

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

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

输入格式:

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

输出格式:

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

输入样例:

20

输出样例:

4

思路：

本题难度不大，关键在于判断素数的程序运算效率要高，不然会出现运行超时

bool judge(int n)
{
    if (n == 2) return true;//2是素数
    if (n % 2 == 0)return false;//其他偶数都不是素数
    for (int i = 3; i <= sqrt(n); i+=2)//从3开始除，步长为2,判断速度加快一倍
    {
        if (n%i == 0)return false;
    }
    return true;
}

代码：

素数对猜想

//1007  素数对猜想
#include<iostream>
#include<vector>
#include<cmath>//关键在于使用sqrt函数简化素数的判断

using namespace std;

bool judge(int n)
{
    if (n == 2) return true;
    if(n % 2 == 0)return false;
    for (int i = 3; i <= sqrt(n); i += 2)
    {
        if (n%i == 0)return false;
    }
    return true;
}

int main()
{
    int N;
    cin >> N;
    if (N <= 2)
    {
        cout << 0;
        return 0;
    }
    vector<int> store;
    for (int i = 2; i <= N; i++)
    {
        if (judge(i)) store.push_back(i);
    }
    vector<int> ::iterator it;
    int count = 0;
    for (it = store.begin() + 1; it != store.end(); it++)
    {
        if ((*it - *(it - 1)) == 2) count++;
    }
    cout << count;
    return 0;
}