PAT B1007 素数对猜想
程序员文章站
2024-03-15 16:03:18
...
1007 素数对猜想 (20 分)
让我们定义dn
为:d(n)=p(n+1)−p(n),其中pi是第i个素数。显然有d1=1,且对于n>1有dn
是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
现给定任意正整数N(<10^5),请计算不超过N的满足猜想的素数对的个
数。
输入格式:
输入在一行给出正整数N。
输出格式:
在一行中输出不超过N的满足猜想的素数对的个数。
输入样例:
20
输出样例:
4
1.以20为例,20以内的素数为1,2,3,5,7,11,13,17,19.其中,3和5,5和7,11和13,17和19四对满足题设,则输出为3.
2.本题关键在于求出输入数以内的所有素数,素数的判断方法为,n不能被2到根号n以内所有整数整除,则n为素数。这里涉及到sqrt()使用
3.储存素数表的数组如果过小,则会产生段错误
#include<stdio.h>
#include<math.h>
int main(){
int j,n;
int prinum[10000]; //保存素数,此处取过小会产生段错误
int len=0;
int sum=0;
int temp;
scanf("%d",&n);
for(int i=1;i<=n;i++){ //找出素数的方法
temp=(int)sqrt((double)i);
for(j=2;j<=temp;j++){
if(i%j==0){
break;
}
}
if(j>temp){
prinum[len++]=i;
}
}
for(int i=0;i<len-1;i++){ //判断每相隔的素数是否相差为2
if(prinum[i+1]-prinum[i]==2)
sum++;
}
printf("%d",sum);
return 0;
}
上一篇: 求n的阶乘
下一篇: python 求100以内的素数