[PAT B] 1007 素数对猜想

1007 素数对猜想

题目

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

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

输入格式:

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

输出格式:

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

输入样例:

20

输出样例:

4

思路分析

暴力检索显然是 O(n^2),但是只要黎曼猜想还叫黎曼猜想,素数分布情况就还是没被完全发掘的

先暴力一下,以后继续寻找其他方法

代码

#include <iostream>

using namespace std;

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

int main() {
    int n;
    int count = 0;
    cin >> n;
    for (int i = 2; i <= n - 2; i++) {
        if (isPrime(i) && isPrime(i + 2)) {
            count++;
        }

    }
    cout << count;
    return 0;
}
本作品采用《CC 协议》,转载必须注明作者和本文链接
一只热爱编程的松鼠
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!