- 【用途】建立質數表,避免費時的除法取餘計算,可供後續程式執行時速查。
- 【實作】
- 可以改成建立non-prime table,初始值全部為false,比較方便。
- a[ ]:檢查並紀錄給定範圍內的每個數是否為質數。
- vector<int> v: 紀錄所有已經判斷的質數,供後續程式使用。
- Line-9:i += j 是關鍵。
- 【範例】ZeroJudge a007: 判斷質數

// 質數篩法 (Sieve of Eratosthenes)
bool a[46342];
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;
}
}
}