JavaScript로 두 수가 서로소(Co-prime)인지 확인하는 방법

서로소(Co-prime)란?

두 수가 서로소(co-prime)라는 것은 두 수 사이에 공통된 소인수가 하나도 존재하지 않는다는 뜻입니다. 단, 1은 소수가 아니므로 여기에는 포함되지 않습니다.

예를 들어 4와 5는 공통 약수가 1뿐이므로 서로소지만, 21과 57은 공통 약수 3을 함께 가지고 있으므로 서로소가 아닙니다.

이번 글에서는 두 개의 숫자를 인자로 받아 서로소 관계이면 true, 그렇지 않으면 false를 반환하는 함수를 JavaScript로 작성해 보겠습니다.

구현 예제

아래 코드는 2부터 두 수 중 큰 값 미만까지의 정수로 두 숫자를 각각 나누어 보며 공통 약수가 존재하는지 검사하는 가장 직관적인 방식입니다.

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

코드 동작 원리

• smaller 변수: 삼항 연산자로 두 수 중 한쪽을 기준값으로 저장합니다. 공통 약수는 두 수 중 작은 값 이하에서만 존재할 수 있으므로, Math.min()을 사용해 반복 범위를 줄이면 성능을 더 개선할 수 있습니다.
• 반복문: 2부터 기준값 미만까지 순회하며 각 정수로 두 숫자를 나누어 봅니다.
• 조건 검사: 같은 수로 두 숫자가 모두 나누어떨어지면(condition1 && condition2) 공통 약수가 존재한다는 뜻이므로 즉시 false를 반환합니다.
• 기본 반환값: 반복문이 끝날 때까지 공통 약수를 찾지 못했다면 두 수는 서로소이므로 true를 반환합니다.

더 효율적인 방법: 최대공약수(GCD) 활용

두 수가 서로소일 필요충분조건은 '최대공약수가 1'이라는 점입니다. 따라서 유클리드 호제법으로 최대공약수를 구하면 반복문 전체를 도는 것보다 훨씬 적은 연산으로 판별할 수 있습니다.

// 유클리드 호제법으로 최대공약수(GCD) 계산
const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));

// 최대공약수가 1이면 서로소
const areCoprimes = (num1, num2) => gcd(num1, num2) === 1;

console.log(areCoprimes(4, 5));   // true
console.log(areCoprimes(21, 57)); // false

입력 값이 커질수록 GCD 방식이 특히 유리하며, 로그 시간 복잡도로 동작하기 때문에 큰 숫자를 다룰 때도 안정적인 성능을 보장합니다.