tag: 素数

以下は、指定された範囲内の素数を生成するシンプルなC言語のコードです。この例では、1からnまでの素数を列挙します。 #include <stdio.h>#include <stdbool.h> bool isPrime(int num) { if (num <= 1) return false; if (num <= 3) return true; if (num % 2 == 0 || num % 3 == 0) return false; for (int i = 5; i * i <= num; i += 6) { if (num % i == 0 || num % (i + 2) == 0) return false; } return true; } void printPrimes(int n) { printf("2 "); for (int i = 3; i <= n; i += 2) { if (isPrime(i)) { printf("%d ", i); } } printf("\n"); } int main() { int n; printf("素数を生成する範囲の最大値を入力してください: "); scanf("%d", &n); printf("1から%dまでの素数は以下の通りです:\n", n); printPrimes(n); return 0; } このコードは以下のように動作します：...

エラトステネスの篩とは エラトステネスの篩とは、ある数以下の素数を列挙するアルゴリズムです。 アルゴリズムは単純で、以下の手順で実装できます。 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!...

Rustで素数を列挙するプログラムを書いてみました。 fn main(){letmax=1000;letmutprimes=vec!...