JavaScriptで2つの数が互いに素（coprime）かどうかを判定する方法

互いに素（coprime）とは

2つの数が「互いに素（ごかいにそ）」であるとは、その2つの数の間に共通の素因数が1つも存在しない関係を指します。なお、1は素数ではないため、共通の素因数としては扱いません。

例えば、4と5は共通の約数が1しかないため互いに素ですが、21と57は両方とも3で割り切れるため、互いに素ではありません。

本記事では、2つの数値を受け取り、互いに素であれば true を、そうでなければ false を返す関数をJavaScriptで実装します。

実装の考え方

基本的なアプローチはシンプルです。2から2つの数のうち小さい方までの各整数について、両方の数を割り切れるかどうかを順番にチェックします。共通の約数が1つでも見つかれば、その2つの数は互いに素ではありません。最後まで共通の約数が見つからなければ、互いに素であると判定できます。

コード例

実際のコードは以下の通りです。

const areCoprimes = (num1, num2) => {
   const smaller = num1 > num2 ? num2 : num1;
   for(let ind = 2; ind < smaller; ind++){
      const condition1 = num1 % ind === 0;
      const condition2 = num2 % ind === 0;
      if(condition1 && condition2){
         return false;
      };
   };
   return true;
};
console.log(areCoprimes(4, 5));
console.log(areCoprimes(9, 14));
console.log(areCoprimes(18, 35));
console.log(areCoprimes(21, 57));

実行結果

コンソールへの出力は以下の通りです。

true
true
true
false

コードの解説

この関数では、まず2つの数のうち小さい方を smaller として取得し、ループの上限としています。これにより不要な計算を省き、効率的に判定できます。

ループ内では、各値 ind が両方の数の約数であるか（剰余が0であるか）を確認し、両方を割り切れる値が見つかった時点で false を返します。ループが完了しても共通の約数が見つからなければ、true を返します。

なお、より大きな数を扱う場合は、ユークリッドの互除法を使って最大公約数（GCD）を求め、それが1かどうかを判定する方法がより効率的です。