本文主要是介绍【PAT (Basic Level) Practice】——【素数】1007 素数对猜想，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

• 一【题目难度】
• 二【题目编号】
• 三【题目描述】
• 四【题目示例】
• 五【解题思路】
• 六【最终得分】
• 七【代码实现】
• 八【提交结果】

一【题目难度】

• 乙级

二【题目编号】

• 1007 素数对猜想 (20 分)

三【题目描述】

• 让我们定义 d n d_n dn​​ 为： d n ​ = p n + 1 ​ − p n d_n​ =p_{n+1}​ −p_n dn​​=pn+1​​−pn​​ ，其中 p i p_i pi​​ 是第 i i i个素数。显然有 d 1 ​ = 1 d_1​ =1 d1​​=1，且对于 n > 1 n>1 n>1有 d n d_n dn​​ 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
• 现给定任意正整数 N ( < 1 0 5 ) N(<10^5 ) N(<105)，请计算不超过 N N N的满足猜想的素数对的个数。

四【题目示例】

• 输入格式:
  输入在一行给出正整数 N N N。

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

• 输入样例:
  20

• 输出样例:
  4

五【解题思路】

• 这个题还是比较好想的，主要思路就是枚举1~n（包括n，因为题目说不超过，所以是≤）中的所有素数，然后遍历判断两个素数是否相邻即可。但是有些小细节需要注意如下：
  ①：要知道1不是素数，虽然2是素数，但是没有能和它配对的，所以2也不计算在内
  ②： f o r for for循环每次的增长为2，原因是从3开始，保证以奇数增长，因为偶数肯定不是素数（除了2），所以之判断奇数即可
  ③：要保证 i & & i + 2 ≤ n i \quad \&\& \quad i+2 ≤ n i&&i+2≤n
  ④：编写判断素数的函数不能直接从头到尾遍历，否则其中有一个用例一直运行超时，所以需要优化：我们知道如果一个数能被2~n之间的任一整数整除，其中有一个因子必然小于等于 m \sqrt{m} m ​，另一个因子必然大于等于 m \sqrt{m} m ​，他们都是成对出现的，所以我们只需要遍历从2到 m \sqrt{m} m ​，如果不是素数，自然有因子被取模等于0，这样就可以判断了，而且速度更快

六【最终得分】

• 20分

七【代码实现】

#include<stdio.h>
#include<stdbool.h>
#include<math.h>

bool isPrimeNumber(int x)
{
    int sqr = (int)sqrt(1.0*x);
    for(int i = 2;i<=sqr;i++)
    {
        if(x % i == 0)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    int n,res = 0;
    scanf("%d",&n);
    for(int i = 3;i + 2 <= n;i+=2)
    {
        if(isPrimeNumber(i)&& isPrimeNumber(i+2))
        {
            res++;
        }
    }
    printf("%d",res);
    return 0;
}

八【提交结果】

这篇关于【PAT (Basic Level) Practice】——【素数】1007 素数对猜想的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！