什麼是埃拉托斯特尼篩法？列舉 1000 以下質數的演算法與實作

什麼是埃拉托斯特尼篩法

埃拉托斯特尼篩法是一種用來找出一定範圍內所有質數的演算法。演算法很簡單，可以透過以下步驟實現：

建立一個包含 N 個元素的布林值陣列，並將所有元素初始化為 true。
將陣列的第 0 個和第 1 個元素設為 false（因為 0 和 1 不是質數）。
如果陣列的第 2 個元素為 true，則輸出 2 為質數。
將陣列中 $2^2$ 以上的 2 的倍數對應的元素全部設為 false ※
如果陣列的第 3 個元素為 true，則輸出 3 為質數。
將陣列中 $3^2$ 以上的 3 的倍數對應的元素全部設為 false。
對於第 4 個、第 5 個，……直到第 N 個元素，重複相同的處理。

※ 將平方以上的元素設為 false 的原因在於，小於平方的數字已經被處理過（列舉已完成）。

Rust 實作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
fn main() {
    let n = 1000;
    let mut is_prime = vec![true; n+1];
    is_prime[0] = false;
    is_prime[1] = false;
    for i in 2..=n {
        if is_prime[i] {
            println!("{}", i);
            let mut j = i * i;
            while j <= n {
                is_prime[j] = false;
                j += i;
            }
        }
    }
}

稍微最佳化版本

考慮到以下幾點，我們進行稍微最佳化的實作：

將陣列初始化為 false 而不是 true（這樣速度更快）。
因為 2 的倍數不是質數，所以省略將 2 的倍數設為 false 的處理。
不需要迴圈到 n，只需列舉到 n 的平方根為止的質數，就能找出所有小於等於 n 的質數。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
fn main() {
    let n = 1000;
    let mut is_prime = vec![false; n+1];
    is_prime[2] = true;
    for i in (3..=n).step_by(2) {
        is_prime[i] = true;
    }
    for i in 3..=((n as f64).sqrt() as usize) {
        if is_prime[i] {
            let mut j = i * i;
            while j <= n {
                is_prime[j] = false;
                j += i * 2;
            }
        }
    }
    for i in (2..=n).filter(|&x| is_prime[x]) {
        println!("{}", i);
    }
}

參考資料

埃拉托斯特尼篩法