欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PAT B1007 素数对猜想

程序员文章站 2024-03-15 16:03:18
...

1007 素数对猜想 (20 分)
让我们定义dn
​​ 为:d​(n)=p​(n+1)−p(​n),其中p​i是第i个素数。显然有d​1=1,且对于n>1有d​n

​​ 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为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;
}