PAT (Basic Level) Practice 1007 素數對猜想

讓我們定義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
           

方法1.因為算法政策的問題會導緻不同的結果，會有一個點逾時

#include<iostream>
#include<string>
#include<vector>
using namespace std;

int main()
{
	int i, n, j;
	vector<int> s;
	cin >> n;

	for (i = 2; i <= n; i++){
		for (j = 2; j <= i; j++)
			if (i%j == 0)
				break;
		if (i == j)
			s.push_back(i);
	}
	int t = 0;
	for (i = 0; i < s.size()-1; i++)
	{
		if (s.at(i + 1) - s.at(i) == 2)
			t++;
	}
	cout << t << endl;

	return 0;
}
           

 方法2.

#include<iostream>
#include<string>
#include<cmath>
using namespace std;

int main()
{
	int i, n, j;
	int p = 2;
	cin >> n;
	int t = 0;

	for (i = 3; i <= n; i++){
		for (j = 2; j <= sqrt(i); j++)
			if (i%j == 0)
				break;
		if (j>sqrt(i)){
			if (i - p == 2)
				t++;
			p = i;
		}
	}
	cout << t;

	return 0;
}