【Codewars】素数にまつわるアルゴリズム問題に取り組んだ記録

最近は毎日Codewarsに取り組んでいます！

Codewarsで学んだこと、もう少し深堀して調べたことを残します。
今回はCodewarsで素数にまつわるアルゴリズム問題を中心にやってみました！

素数かどうか

...素数ってなんだっけ...

素数とは

素数（そすう、英: primeあるいはprime number）とは、2 以上の自然数で、正の約数が 1 と自分自身のみであるもののことである。正の約数の個数が 2 である自然数と言い換えることもできる。1 より大きい自然数で素数でないものは合成数と呼ばれる。

https://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0

for文を使用して、約数を洗い出して最終的な個数によって素数かどうかを判断してみる
初期値を2にして、引数(n)以下であればループを続ける条件で。

function isPrime(n) {
  if (n < 2) return false;
  let arr = [];
  for (let i = 2; i < n; i++) {
    if (n % i === 0) {
      arr.push(i);
    }
  }
  return arr.length === 0;
}

console.log(isPrime(0)); // false
console.log(isPrime(1)); // false
console.log(isPrime(2)); // true
console.log(isPrime(12)); // false

双子素数かどうか

...双子素数ってなに...

双子素数とは

双子素数（ふたごそすう、英: twin prime）とは、差が 2 である二つの素数の組を構成する各素数のことである。双子素数の組は、(2, 3) を除いた、最も近い素数の組である。双子素数を小さい順に並べた列は、次のとおりである。

https://ja.wikipedia.org/wiki/%E5%8F%8C%E5%AD%90%E7%B4%A0%E6%95%B0

対象の値にプラス2、マイナス2した値のどちらかが素数であれば双子素数となるのでsomeを使用しました。

function isTwinPrime(n) {
  const f = (num) => {
    if (num < 2) return false;
    for (let i = 2; i < num; i++) {
      if (num % i === 0) return false;
    }
    return true;
  };

  if (!f(n)) return false;
  return [n + 2, n - 2].some((a) => f(a));
}

console.log(isTwinPrime(19)); // true
console.log(isTwinPrime(953)); // false

ウィルソン素数かどうか

ウィルソン素数とは

ウィルソン素数（ウィルソンそすう、英: Wilson prime）とは、p_2 が (_p − 1)! + 1 を割り切るような素数 p である。ここで "!" は階乗。任意の素数 p が (p − 1)! + 1 を割り切ることはわかっている（ウィルソンの定理）。名称はイングランドの数学者ジョン・ウィルソン（英語版）にちなむ。

https://ja.wikipedia.org/wiki/%E3%82%A6%E3%82%A3%E3%83%AB%E3%82%BD%E3%83%B3%E7%B4%A0%E6%95%B0

((P-1)! + 1) / (P * P)をコードで実現する!
階乗部分はfor文でできそう

function amIWilson(p) {
  const getFactorial = (num) => {
    let factorial = 1;
    for (let i = num; i > 0; i--) {
      factorial *= i;
    }
    return factorial;
  };
  return (getFactorial(p - 1) + 1) % (p * p) === 0;
}

console.log(amIWilson(5)); // true
console.log(amIWilson(9));  // false
console.log(amIWilson(6));  // false

上記のコードでも実装できたのですが
inputする値が大きくなった場合に階乗した値がInfinityになってしまい、意図した解にならなくなってしまいました...

function amIWilson(p) {
  const getFactorial = (num) => {
    let factorial = 1;
    for (let i = num; i > 0; i--) {
      factorial *= i;
    }
    return factorial;
  };
  return (getFactorial(p - 1) + 1) % (p * p) === 0;
}

console.log(amIWilson(563)); // false

ウィルソン素数について...

ウィルソン素数について調べていると、現在知られているウィルソン素数がわかりました

現在まで知られているウィルソン素数は5、13、563だけです。

なので、この知識があれば以下のように書くことができます。

function amIWilson(p) {
  return [5, 13, 536].includes(p);
}


console.log(amIWilson(5)); // true
console.log(amIWilson(9));  // false
console.log(amIWilson(6));  // false

まとめ

今回は素数に関係するアルゴリズム問題にチャレンジしました。
まずは8kyuや7kyuの問題から挑戦してみました