題目敘述：https://zerojudge.tw/ShowProblem?problemid=a007
解題想法： 質數篩法 (Sieve of Eratosthenes)
- 看似簡單的質數判斷問題，可是會TLE，因為測試資料至多有200000筆。
- 因為輸入數字 <= 2147483647，單純建立質數表的方式會超出題目的記憶體限制 512 MB。
- 分成兩部份處理：
- sqrt(2147483647) = 46341
- <= 46341 的數字，透過質數表 (a[ ]) 查詢。
- 建立質數表的同時，把質數存入vector (v) 中。
- > 46341 的數字，測試其是否有「v」中的任何因數，有的話，可以提早結束迴圈。
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
bool a[46342];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
vector <int> v;
for (int j = 2; j < 46342; j++){
if (!a[j]){
v.push_back(j);
for (int i = j * j; i < 46342; i += j){
a[i] = true;
}
}
}
while (cin >> n){
if (n > 46341){
m = sqrt(n);
bool flag = true;
for (int i:v){
if (n % i == 0){
flag = false;
cout << "非質數\n";
break;
}
}
if (flag) cout << "質數\n";
}else{
if (a[n]) cout << "非質數\n";
else cout << "質數\n";
}
}
return 0;
}