1007 素数对猜想

1007 素数对猜想 (20 分)

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

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

输入格式:

输入在一行给出正整数N

输出格式:

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

输入样例:

20

输出样例:

4
#include<stdio.h>
#include<math.h>
int fac(int n)//判断是否为素数
{
	int i;
	
	if(n==1)
		return 0;
	if(n==2)
		return 1;
	if(n%2==0)
		return 0;
	for(i=2;i<=sqrt(n)+1;i++)
	{
		if(n%i==0)
		return 0;
	} 
	return 1;
}
int main()
{
	int n,i;
	int num=0;
	
	scanf("%d",&n);
	for(i=3;i<=n;i++)
		if(fac(i))
			if(fac(i+2)&&i+2<=n)
				num++;
	printf("%d",num);
}