PAT（乙級） 1007 素數對猜想

題目描述

讓我們定義d​[n]為：d​[n]​​ =p[n+1]​​ − p[n]​ ，其中p[i]​​ 是第i個素數。顯然有d[1]​​ =1，且對于n>1有d[​n]​​ 是偶數。“素數對猜想”認為“存在無窮多對相鄰且差為2的素數”。現給定任意正整數N(<100000​​ )，請計算不超過N的滿足猜想的素數對的個數。

輸入格式

輸入在一行給出正整數N。

輸出格式

在一行中輸出不超過N的滿足猜想的素數對的個數。

輸入樣例

20

輸出樣例

4

解題思路

（1）編寫一個判斷是否為素數的函數。

（2）對小于輸入n的所有數字進行判斷，若為素數，使用vector進行記錄

（3）對相鄰的素數進行判斷，若滿足素數對猜想，則結果加一，注意将結果初始化為0

程式源碼

#include <iostream>
#include <vector>
using namespace std;
//判斷是否為素數 
int prime(int n){
	int i;
	if(n<2)
		return 0;
	for(i = 2; i*i <= n; i++)
		if(n%i == 0)
			return 0;
	return 1;		
}

int main()
{
	vector<int> a;  //存儲小于輸入n的素數 
	int n, count = 0;
	cin>>n;
	for(int i = 2; i <= n; i++)
		if(prime(i))
			a.push_back(i);
	int len = a.size();
	for(int i = 0; i < len-1; i++)
		if(a[i+1] - a[i] == 2)	//判斷相鄰兩素數之差是否為2 
			count++;
	cout<<count;
	return 0;
}