【筆記】Sieve of Eratosthenes 質數篩法

  • 【用途】建立質數表,避免費時的除法取餘計算,可供後續程式執行時速查。
  • 【實作】
    • 可以改成建立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;
        }
    }
}
分享本文 Share with friends