エラトステネスの篩を使って1000以下の素数を列挙する方法
エラトステネスの篩とは エラトステネスの篩とは、ある数以下の素数を列挙するアルゴリズムです。 アルゴリズムは単純で、以下の手順で実装できます。 Nの要素をもつbool値配列を作成し、全要素をtrueで初期化する 配列の0番目と1番目の要素をfalseにする(0と1は素数ではないため) 配列の2番目の要素がtrueなら、2を素数として出力する 配列の$2^2$以上の2の倍数番目の要素をすべてfalseにする※ 配列の3番目の要素がtrueなら、3を素数として出力する 配列の$3^2$以上の3の倍数番目の要素をすべてfalseにする 4番目、5番目、・・・、N番目の要素について、同様の処理を繰り返す ※2乗以上の要素をfalseの対象としているのは、2乗より小さい数についてはすでに処理済み(列挙が完了している)であるためです。 Rustでの実装 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; } } } } 少し高速化版 下記の点を考慮して、少し高速化した実装を行います。 配列の初期化をtrueで初期化するのではなく、falseで初期化する（このほうが高速） 2の倍数は素数ではないので、2の倍数の要素をfalseにする処理を省略 nまでループする必要はなく、nの平方根までの素数を列挙すれば、n以下の素数を列挙できる fn main() { let n = 1000; let mut is_prime = vec!...
