素数大学《素数判定》

素数メニュー【エラトステネスの篩・グロタンディーク素数・フェルマーテスト・素数判定・大きな数の素数判定・素数大学】

問題【STEP: 1】グロタンディーク素数
Task
57 が素数である場合には″YES″・素数でない場合は″NO″を出力してね。

【グロタンディーク素数】コード

const n = 57;
let prime = true;  // 素数か否かの真偽値を true で初期化
for (let i = 2; i * i <= n; i++) {  // ループの範囲は 2 ~ n の平方根
// for (let i = 2; i <= Math.sqrt(n); i++) {
   if (n % i === 0) {  // n が i で割り切れれば…
      prime = false;  // n は 素数に該当しないので prime は false
      break;
   }
}
console.log(prime ? 'YES' : 'NO');
hogeちゃんの画像

57 は 3 で割り切れるので 素数じゃなかった。

top
問題【STEP: 2】素数判定
Task
整数 N が素数かどうかを判定してね。

【素数判定】コード

reader.on('close', () => {
   const N = Number(lines[0]);
   let prime = true;  // 素数か否かの真偽値を true で初期化
   if (N === 1) {  // N が 1 の場合…
      prime = false;  // 素数に該当しない(例外処理)
   }
   for (let i = 2; i * i <= N; i++) {  // ループの範囲は 2 ~ N の平方根
// for (let i = 2; i <= Math.sqrt(N); i++) {
      if (N % i === 0) {  // N が i で割り切れれば…
         prime = false;  // N は 素数に該当しないので prime は false
         break;
      }
   }
   console.log(prime ? 'YES' : 'NO');
});
hogeちゃんの画像

N の値を入力から受け取っていますが 【STEP: 1】と ほぼ 同じです。

top
問題【STEP: 3】大きな数の素数判定
Task
整数 N (大きな数)が素数かどうかを判定してね。

【大きな数の素数判定】コード

reader.on('close', () => {
   const N = Number(lines[0]);
   let prime = true;
   if (N === 1) {  // N が 1 の場合…
      prime = false;  // 素数に該当しない(例外処理)
   }
   for (let i = 2; i * i <= N; i++) {  // ループの範囲は 2 ~ N の平方根
// for (let i = 2; i <= Math.sqrt(N); i++) { 
      if (N % i === 0) {  // N が i で割り切れれば…
         prime = false;  // N は 素数に該当しないので prime は false
         break;
      }
   }
   console.log(prime ? 'YES' : 'NO');
});
hogeちゃんの画像

大きな数になっても【STEP: 2】と同じコードで通過できました。

(´・∀・)?

top
問題【STEP: 4】エラトステネスの篩
Task
エラトステネスの篩を用いて整数 N が素数かどうかを判定してね。

【エラトステネスの篩】コード

reader.on('close', () => {
   const N = Number(lines[0]);
   const prime = new Array(N + 1).fill(true);  // 0 ~ N の素数か否かをtrueで初期化
   [prime[0], prime[1]] = [false, false];  // 0 と 1 は 2 以下なので素数に該当しない
   for (let i = 2; i * i <= N; i++) {  // ループの範囲は 2 ~ N の平方根
   // for (let i = 2; i <= Math.sqrt(N); i++) {
      if(!prime[N]){  // prime[N] が 素数に該当しないことがわかっていれば…
         break;  // 処理を止める
      }
      if (prime[i]) {  // prime[i]が初期値(true)のときのみ実行
         for (let j = 2; j * i <= N; j++) {  // j * i が N 以下の間 ループ
            prime[i * j] = false;  // 2つの値を乗算した値は素数に該当しない
         }
      }
   }
   console.log(prime[N] ? 'YES' : 'NO');
});
hogeちゃんの画像
素数判定の漸化式バージョンですね。
top
問題【STEP: 5】フェルマーテスト
Task
整数  N が素数かどうかをフェルマーテストを用いて判定してね。

【フェルマーテスト】コード

reader.on('close', () => {
   const N = Number(lines[0]);  
   const a = 2;  // 2 ~ N-1 の範囲内の数値 → 2に設定
   let fermat = 1;  // fermat (a^(N-1) % N を求めるための変数)を1で初期化
   let prime = true;
   if (N % a === 0) {  // N が a で割り切れる場合
      prime = false;  // N は素数に該当しない
   }
  // a^(N-1) % N を求めるためのループ(fermat * a % N を N - 1 回 繰り返す)
   for (let i = 1; i < N; i++) {
      fermat = fermat * a % N;
   }
   if (fermat % N !== 1) {  // a^(N-1) % N が 1 でない場合
      prime = false;  // N は素数に該当しない
   }
   console.log(prime ? 'YES' : 'NO');
});
hogeちゃんの画像

フェルマーテスト…。整数 N が素数であるかを高確率で判定する方法の 1 つ。だそうです。

top
問題【FINAL】素数大学
Task
受験番号が素数なら合格・素数でければ不合格。合否を判定をしてね。

【素数大学】コード

reader.on('close', () => {
   const N = Number(lines[0]);  // 受験者数
   const A = [];  // 受験番号(素数なら合格)
   for (let i = 1; i <= N; i++) {
      A.push(Number(lines[i]));  // A に 受験番号を保存
   }
// エラトステネスの篩 ここから
   const M = Math.max(...A);  // 受験番号の最大番号
   const prime = new Array(M + 1).fill(true);  // 受験番号の最大番号までの素数であるかどうかの真偽値
   [prime[0], prime[1]] = [false, false];  // 2 以下は素数に該当しないので false
   for (let i = 2; i * i <= M; i++) {  // ループの範囲は 2 ~ M の平方根
   // for (let i = 2; i <= Math.sqrt(M); i++) {
      if (prime[i]) {  // prime[i]が初期値(true)のときのみ実行
         for (let j = 2; j * i <= M; j++) {  //  j * i が N 以上になるまで ループ
            prime[i * j] = false;  // 2つの値をかけ合わせた値は素数に該当しない
         }
      }
   }
// エラトステネスの篩 ここまで
   A.forEach(a => {
      console.log(prime[a] ? 'pass' : 'failure');
   });
});
hogeちゃんの画像

あらかじめ primeに 0〜A の最大値 までの素数であるかどうかの真偽値を保存して エラトステネスの篩で処理。forEach()で A の各値が素数に該当するかどうかを出力しています。

top

コメント