PAT Basic Level 1007 素數對猜想 （20 分）

題目連結:

https://pintia.cn/problem-sets/994805260223102976/problems/994805317546655744

AC代碼:

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int maxn = 1000100;
int Prime_group[maxn];
bool prime_chane[maxn] = { false };


int main() {
	int n;
	cin >> n;
	int pNum = 0;
	for (int i = 2; i <= n; i++) {//求1~n的素數數組,判斷條件是i<=n,不是i<n,否則,測試點3出錯,18分
                                //舉例:n=31時,若i<=n,則輸出5,若i<n,則輸出4
                                //29和31 均為素數,
		if (!prime_chane[i]) {
			Prime_group[pNum++] = i;
			for (int j = i + i; j < maxn; j += i) {
				prime_chane[j] = true;
			}
		}
	}
	int cnt = 0;
	for (int i = 1; i < pNum; i++) {
		if (Prime_group[i] - Prime_group[i - 1] == 2)
			cnt++;
	}
	cout << cnt << endl;
}