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

PAT B 1007 素数对猜想

程序员文章站 2024-03-15 15:53:41
...

1007 素数对猜想

(20 分)
让我们定义dn为:dn=p(n+1)−p(n),其中pi
​​ 是第i个素数。显然有d1=1,且对于n>1有dn​ 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

现给定任意正整数N(<10^5​​ ),请计算不超过N的满足猜想的素数对的个数

输入格式:

输入在一行给出正整数N。

输出格式:

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

输入样例:
20
输出样例:
4

#include<stdio.h>
#include<math.h> 
int main(){
	long int n;
	scanf("%ld",&n);
	int i,j,x=3,y=0,m;
	// 从5开始寻找素数对 
	for(i=5;i<=n;i++){
		//寻找素数		
		m=sqrt(i);// 素数平方根 
		for(j=2;j<=m;j++){
			if(i%j==0) {
				break;
			}
		}
		
		//当i为素数时 
		if(j>m){
			// 两素数差为2,计数增加1 
			if(i-x==2){
				y++;
			};
			//记录当前素数 
			x=i;
		}
	}
	
	printf("%d",y);
	
	return 0;
}

上一篇: 剑指offer-求a^n

下一篇: 123