PAT. 1007 素數對猜想

**

1007 素數對猜想 （20 分)

**

讓我們定義d​n為：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

思路：寫一個判斷素數的函數，判斷i和i+2是否都是素數即可，注意是求素數對的個數，兩個素數算一個素數對。

#include<stdio.h>
#include<math.h>

int isprime(int n)
{
	if(n < 2)
		return 0;
	int i, m = sqrt(n);
	for(i = 2; i <= m; i++)
		if(n % i == 0)
			return 0;
	return 1;
}

int main()
{
	int n, i, sum = 0;
	scanf("%d", &n);
	for(i = 2; i <= n - 2; i++)      //i的範圍，避免i超過n
	{
		if(isprime(i) && isprime(i + 2))    //i+2<=n
			sum += 1;
	}
	printf("%d\n", sum);
	return 0;
}