Rustでエラトステネスの篩をやってみる

rust

素数判定のアルゴリズムで有名なエラトステネスの篩をRustで実装してみました。

ネットで見るとjavascriptで実装したのが公開されていたいるすけど、まぁ結構遅い。しょうがないよねjavascriptだからさ。

で、今回はRustで実装したら、どんなもんかなーって思ってね。

では、いってみましょう!

エラトステネスの篩

まずは、エラトステネスの篩の簡単な説明から

エラトステネスの篩は、指定した数(n)以下の素数を判定する方法

小さい方から順番にその素数倍数を消去(篩にかける)する、消去されていない数字に移動して、同じ操作をする、この操作を\(sqrt(n)\)に達するまで繰り返すと、n以下の素数が判明するよっていう方法。

詳しくはググってね。

(説明するっていって、最後はググれって。もうめちゃくちゃだよね)

rustでエラトステネスの篩の実装

エラトステネスの篩では、素数じゃない数、合成数を消去(篩にかける)操作、それを\(sqrt(n)\)まで繰り返す操作が出てくる。

そして、実装するときは最後に素数リストを作らなきゃいけないよね。

この3つの部分をそれぞれ作っていきましょう。

篩の実装

篩の部分を実装していきましょう。

sieve_composite_numberっていう名前の関数を作ります

引数は、1からnまで入ったベクタと素数

そして、篩にかけた1からnまで入ったベクタを返り値として出力します。

fn sieve_composite_number(mut nums:Vec<i64>,prime_number:i64)->Vec<i64>{
    let mut idx:usize = prime_number as usize-1;
        while idx <nums.len()-prime_number as usize{
            idx+=prime_number as usize;
            nums[idx]=0;
        }
    nums
}

ベクタのインデックスに変更するために素数を受け取る引数prime_numberから1を引きます。rustは添え字が0から始まるからね。

与えられた素数(p)は消しちゃダメだから、最初にインデックスをp分だけ進めてスタートします。

これをベクタの最後までやっていきます。

地味だね。

素数を見つけて繰り返す

素数を見つけて、それを\(sqrt(n)\)まで繰り返す操作を実装しましょう。

let end = (end_num as f64).sqrt().floor() as usize;

for i in 1..end{
    if nums[i]!=0{
        nums = sieve_composite_number(nums, i as i64+1);
    }
}

まずは終着点を計算します。\(sqrt(n)\)を切り上げしてusizeにキャストしておきます。

そして、1から最後までforループで回していきます。添え字0番目は数字の「1」なので、飛ばして添え字1番目「2」からスタートだよね。

そして、0以外の場合、篩操作をしてね。ってことで書いておきます。

素数リストを作成

素数リストを作成します。

let mut prime_numbers:Vec<i64>=Vec::new();
for i in 0..nums.len(){
    if nums[i]!=0{
        prime_numbers.push(nums[i]);
    }
}

まずは、空の素数リストを作って

そのあと数字のベクタnumsから0以外の数字を拾い上げて、素数のリストに順次追加していきます。

これで、素数のリストが完成します。

n以下の素数を返す関数を作る

この3つを合わせて、n以下の数の素数を返す関数を作ります。

get_prime_numbersっていう関数にしましょう

fn get_prime_numbers(end_num:i64)->Vec<i64>{
    let mut nums:Vec<i64>=Vec::new();
    for i in 1..=end_num{
        nums.push(i)
    }
    nums[0]=0;

    let end = (nums.len() as f64).sqrt().floor() as usize;
    for i in 1..end{
        if nums[i]!=0{
            nums = sieve_composite_number(nums, i as i64+1);
        }
    }


    let mut prime_numbers:Vec<i64>=Vec::new();
    for i in 0..nums.len(){
        if nums[i]!=0{
            prime_numbers.push(nums[i]);
        }
    }
    prime_numbers
}

最初に1からnまでの自然数のベクタを作ります。

次に素数を探して、そしてその素数の倍数を篩にかけるそうさをして

最後に素数のベクタを作って返り値として返します。

素数を求めてみる

では、実際に作った関数を使って1000以下の素数を求めてみましょう

プログラム全体はこんな感じ

fn main() {
    let prime_numbbers = get_prime_numbers(1000);
    println!("{:?}",prime_numbbers);
}

fn sieve_composite_number(mut nums:Vec<i64>,prime_number:i64)->Vec<i64>{
    let mut idx:usize = prime_number as usize-1;
        while idx <nums.len()-prime_number as usize{
            idx+=prime_number as usize;
            nums[idx]=0;
        }
    nums
}

fn get_prime_numbers(end_num:i64)->Vec<i64>{
    let mut nums:Vec<i64>=Vec::new();
    for i in 1..=end_num{
        nums.push(i)
    }
    nums[0]=0;

    let mut prime_numbers:Vec<i64>=Vec::new();
    let end = (nums.len() as f64).sqrt().floor() as usize;
    for i in 1..end{
        if nums[i]!=0{
            nums = sieve_composite_number(nums, i as i64+1);
        }
    }
    for i in 0..nums.len(){
        if nums[i]!=0{
            prime_numbers.push(nums[i]);
        }

    }
    prime_numbers

}

では実行!

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

結構一瞬で出てきます。

1億とかにするとちょっと待つけどね。

まとめ

エラトステネスの篩をRustで実装してみました。

実装の仕方はいろいろあって、これが一つの方法ではないですね。

素数かどうかっていう構造体みたいのを作って判定してみたり、もっとシンプルなものもあるかもしれません。

まぁいろいろチャレンジしてみてねー

コメント

タイトルとURLをコピーしました