文章目录
一【题目难度】
- 乙级
二【题目编号】
- 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;
}