【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e913
【解題想法】
- 本題每次只會輸入單筆測資。
- 一邊建立質數表，一邊判斷比目前質數 (i) 小2的數 (i – 2) 如果同為質數，則把 i 加進vector。
- v.size() 即為答案。
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
//初始化
int p[n+1];
for (int i = 0; i <= n; i++) p[i] = 0;
p[0] = 1;
p[1] = 1;
//質數篩法
vector <int> v;
for (int i = 2; i <= n; i++){
if (p[i] == 0){
if (p[i-2] == 0) v.push_back(i);
for (int j = i+i; j <= n; j+=i){
p[j] = 1;
}
}
}
cout << v.size() << "\n";
return 0;
}