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

2つの数が「互いに素（コプライム）」であるとは、それらの間に共通の素因数が存在しないことを意味します。なお、1は素数ではないため、共通因数としてカウントされません。

互いに素とは

具体的な例を見てみましょう。

4 と 5 → 互いに素
9 と 14 → 互いに素
18 と 35 → 互いに素
21 と 57 → 互いに素ではない（共通の素因数 3 を持つため）

実装の方針

ここでは、2つの数を受け取り、それらが互いに素であれば true を、そうでなければ false を返す関数を作成します。

判定のアプローチはシンプルです。2つの数のうち大きい方までの各整数（2から順に）について、両方の数がその値で割り切れるかどうかを確認します。割り切れる値が1つでも見つかれば、それは共通の因数となるため、互いに素ではありません。

コード例

const areCoprimes = (num1, num2) => {
    const smaller = num1 > num2 ? num1 : num2;
    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

最初の3つの組み合わせは共通の素因数を持たないため true が返され、21と57はどちらも3で割り切れるため false が返されていることがわかります。

補足：より効率的な判定方法

上記の方法は直感的で理解しやすい一方、計算量は O(n) です。大きな数を扱う場合は、ユークリッドの互除法を使って最大公約数（GCD）を求め、それが1であるかどうかを判定する方法がより高速です。

const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
const areCoprimesEuclid = (num1, num2) => gcd(num1, num2) === 1;

このように、GCDが1であれば2つの数は互いに素であると定義できるため、こちらの方法も覚えておくと便利です。