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;
}