Featured image of post Rustで素数を列挙するプログラムの作成方法とコード例
プログラミング

Rustで素数を列挙するプログラムの作成方法とコード例

既知の素数で試し割りし、上限以下の素数をRustで列挙します。0・1・2の境界、平方根までの判定、ベクタの反復処理と加算の範囲を説明します。

見つけた素数を保存し、それらで試し割りするRustの例です。primes_up_to(max) は上限を含む素数の一覧を返します。1000以下では168個で、0と1は素数に含めません。これは篩の実装ではありません。

コード

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

fn primes_up_to(max: usize) -> Vec<usize> {
    if max < 2 {
        return Vec::new();
    }
    let mut primes = vec![2];
    let mut n = 3;
    while n <= max {
        let mut is_prime = true;
        for &p in &primes {
            if p > n / p {
                break;
            }
            if n % p == 0 {
                is_prime = false;
                break;
            }
        }
        if is_prime {
            primes.push(n);
        }
        if max - n < 2 {
            break;
        }
        n += 2;
    }
    primes
}

fn main() {
    for p in primes_up_to(1000) {
        println!("{}", p);
    }
}

実行と小さな上限

primes.rs として保存し、rustc --edition=2021 primes.rs -o primes でコンパイルします。Windowsでは実行ファイル名を primes.exe にします。実行すると168行を出力し、最初は2、最後は997です。Rust 1.90.0で動作を確認した例です。

primes_up_to(0) と primes_up_to(1) は空のベクタ、primes_up_to(2) は [2]、primes_up_to(3) は [2, 3]、primes_up_to(10) は [2, 3, 5, 7] です。usize を使うので負の上限は引数の型に含まれません。標準入力を解析するプログラムではありません。

判定とループの仕組み

  1. 上限が2未満なら空の結果を返します。それ以外では2を保存し、3から上限以下の奇数だけを調べます。上限を確認してから候補を処理するため、上限2で3を追加しません。
  2. 候補 n が合成数なら、平方根以下の素因数があります。それらの素数は、より小さい候補を処理した段階ですでに一覧に入っています。割り切れたら合成数として止め、割り切れずに p > n / p になったら、それ以上の試し割りは不要です。正の整数の除算で平方根の条件を表し、p * p や浮動小数点の平方根は使いません。
  3. for &p in &primes は一覧を借用して参照を順に受け取り、usize の値を p にコピーします。ループ終了後にだけ新しい素数を追加します。最後の for p in primes_up_to(1000) は、返されたベクタの値を取り出して表示します。RustのVecドキュメントには借用時と所有時の反復処理の違いが示されています。
  4. n <= max の中では max - n は負になりません。残りが2未満なら加算前に終了し、それ以外でだけ n += 2 を行うので上限を超える加算を避けられます。

適用範囲

元の固定値1000のコードも正しく168個を出力します。ただし、そのまま上限を0・1・2へ変えると、処理の前に上限を確認しないため範囲外の2や3を出力していました。ここでは関数として再利用できるように、その境界を扱っています。

一覧の要素数は見つかった素数の個数で、各要素は usize です。ベクタの管理情報と確保容量も必要です。試し割り回数には、除算を1操作と数える粗い上界として O(max sqrt(max)) を考えられますが、これは実測時間やビット計算量ではありません。上限が大きいほど時間と記憶領域が必要で、任意に大きい上限を短時間で列挙できる保証はありません。広い範囲の列挙にはエラトステネスの篩の記事も参照してください。暗号用の素数生成器ではありません。

comments powered by Disqus