一、题目:
让我们定义dn为:dn=pn+1−pn,其中pi是第i个素数。显然有di=1,且对于n>1有dn是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
现给定任意正整数N(<105),请计算不超过
N
的满足猜想的素数对的个数。
二、输入格式:
输入在一行给出正整数N
。
输出格式:
在一行中输出不超过N
的满足猜想的素数对的个数。
三、输入样例:
20
输出样例:
4
四、设计思路:
由于题目的要求是相邻且相差为二的素数,所以我们可以直接令前面一个数为i,后面一个数就为i+2,
然后判断这两个数是否都是素数,如果是的话,那么统计素数对的变量就加1;外面再嵌套一个do-while
循环就ok了,注意循环的终止条件是i+2<=num,而不是i<=num,如果是i<=num的话,那么可能就会越界,
不满足题目的要求,还有一点就是在素数的判断的函数中,如果将判断素数的循环条件变为以下代码:
for(i=2;i<num;i++)
if(num%i==0){flag=0;break;}
虽然最后的结果不会出现问题,但是对程序的时间复杂度会有很大的影响,我在网上做这道题时最开始就是这么写的,
由于那个网站的对程序运行的时间有限制,所以这样写就不能通过,需要改善代码降低时间复杂度才能通过,于是
我就想对素数判断的函数的循环进行改进,本质上就是减少了循环的次数,改进后的代码如下:
for(i=2;i<=sqrt(num);i++)if(num%i==0){flag=0;break;}
五、完整代码:
#include<stdio.h>
#include<math.h>
int JudgePrimeNum(int num);
int main()
{
int num;
int i=1;
int flag=0;
scanf("%d",&num);
do
{
if(JudgePrimeNum(i)==1&&JudgePrimeNum(i+2)==1)
flag=flag+1;
i++;
} while (i+2<=num);
printf("%d",flag);
return 0;
}
//判断数字是否为素数
int JudgePrimeNum(int num)
{
int flag=1;
if(num==1){
flag=0;
}
else if(num==2||num==3){
flag=1;
}
else{
int i;
for(i=2;i<=sqrt(num);i++)
if(num%i==0){
flag=0;
break;
}
}
return flag;
}
六、输出效果:
文章来源: 博客园
- 还没有人评论,欢迎说说您的想法!