PAT 1007 素数对猜想

小咪咪 2022-08-18 02:37 91阅读 0赞

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

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

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

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

输入样例：

20

输出样例：

4

代码实现：

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <cstring>
    
    using namespace std;
    
    /* 判断一个数是不是素数 */
    bool isPrimeNum(const int num)
    {
        if(num == 2)
        {
            return true;
        }
    
        int len = (int)sqrt(num);
        int i = 0;
    
        for(i = 2; i <= len; i++)
        {
            if(num % i == 0)
            {
                return false;
            }
        }
    
        return true;
    }
    
    int main()
    {
        int N = 0;
        int i = 0, counts = 0;
        int lastPrime = 0;
    
        cin >> N;
    
        for(i = 3; i <= N; i++)
        {
            /* 如果是素数 */
            if (true == isPrimeNum(i))
            {
                /* 判断是否符合条件 */
                if (i - lastPrime == 2)
                {
                    counts++;
                }
    
                lastPrime = i;
            }
        }
    
        cout << counts << endl;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，91人围观）

还没有评论，来说两句吧...

相关阅读

相关 1007 素数对猜想

include<stdio.h> include<math.h> int main() { int n,a[100000],k,

旧城等待，/ 2023年10月09日 10:43/ 0 赞/ 12 阅读

相关 1007. 素数对猜想 (20)

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

Bertha 。/ 2022年08月23日 05:46/ 0 赞/ 163 阅读

相关 1007. 素数对猜想 (20)

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

曾经终败给现在/ 2022年08月23日 00:51/ 0 赞/ 199 阅读

相关 PAT 1007 素数对猜想

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

小咪咪/ 2022年08月18日 02:37/ 0 赞/ 92 阅读

相关 1007. 素数对猜想 (20)

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

Love The Way You Lie/ 2022年06月15日 10:13/ 0 赞/ 174 阅读

相关 1007. 素数对猜想 (20)

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

野性酷女/ 2022年05月31日 13:57/ 0 赞/ 215 阅读

相关 1007. 素数对猜想 (20)

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

向右看齐/ 2022年05月27日 01:41/ 0 赞/ 187 阅读

相关 PAT乙级1007：素数对猜想

题目： ![70][] 解题思路： > 把不超过N的素数全部保存在容器中，再验证相邻素数的差值是否为2. 题解： include<iostrea

叁歲伎倆/ 2022年05月09日 12:28/ 0 赞/ 203 阅读

相关 PAT_B_1007 素数对猜想

题目描述：让我们定义dn 为：dn =pn+1 −pn ，其中pi 是第i个素数。显然有d1 =1，且对于n>1有d

爱被打了一巴掌/ 2021年11月01日 08:28/ 0 赞/ 279 阅读

相关 PAT 1007 素数对猜想 (20 分)（Java）

题目描述： ![在这里插入图片描述][20190822202034429.png] 输入格式: 输入在一行给出正整数N。输出格式: 在一行中输出

我不是女神ヾ/ 2021年09月23日 05:50/ 0 赞/ 278 阅读