素数判定のアルゴリズムで有名なエラトステネスの篩をRustで実装してみました。
ネットで見るとjavascriptで実装したのが公開されていたいるすけど、まぁ結構遅い。しょうがないよねjavascriptだからさ。
で、今回はRustで実装したら、どんなもんかなーって思ってね。
では、いってみましょう！
エラトステネスの篩
まずは、エラトステネスの篩の簡単な説明から
エラトステネスの篩は、指定した数（ｎ）以下の素数を判定する方法
小さい方から順番にその素数倍数を消去（篩にかける）する、消去されていない数字に移動して、同じ操作をする、この操作を\(sqrt(n)\)に達するまで繰り返すと、ｎ以下の素数が判明するよっていう方法。
詳しくはググってね。
（説明するっていって、最後はググれって。もうめちゃくちゃだよね）
rustでエラトステネスの篩の実装
エラトステネスの篩では、素数じゃない数、合成数を消去（篩にかける）操作、それを\(sqrt(n)\)まで繰り返す操作が出てくる。
そして、実装するときは最後に素数リストを作らなきゃいけないよね。
この3つの部分をそれぞれ作っていきましょう。
篩の実装
篩の部分を実装していきましょう。
sieve_composite_numberっていう名前の関数を作ります
引数は、1からｎまで入ったベクタと素数
そして、篩にかけた１からｎまで入ったベクタを返り値として出力します。
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)は消しちゃダメだから、最初にインデックスをｐ分だけ進めてスタートします。
これをベクタの最後までやっていきます。
地味だね。
素数を見つけて繰り返す
素数を見つけて、それを\(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番目「２」からスタートだよね。
そして、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以外の数字を拾い上げて、素数のリストに順次追加していきます。
これで、素数のリストが完成します。
ｎ以下の素数を返す関数を作る
この3つを合わせて、ｎ以下の数の素数を返す関数を作ります。
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からｎまでの自然数のベクタを作ります。
次に素数を探して、そしてその素数の倍数を篩にかけるそうさをして
最後に素数のベクタを作って返り値として返します。
素数を求めてみる
では、実際に作った関数を使って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で実装してみました。
実装の仕方はいろいろあって、これが一つの方法ではないですね。
素数かどうかっていう構造体みたいのを作って判定してみたり、もっとシンプルなものもあるかもしれません。
まぁいろいろチャレンジしてみてねー
コメント