자바스크립트(JavaScript)로 서로소(Co-prime) 확인하기

두 수가 서로소(co-prime)라는 것은 두 수 사이에 공통된 소인수가 존재하지 않는다는 의미입니다. 참고로 1은 소수가 아니기 때문에 소인수에 포함되지 않습니다.

서로소의 예시

4와 5는 서로소입니다
9와 14는 서로소입니다
18과 35는 서로소입니다
21과 57은 공통 소인수인 3을 가지고 있으므로 서로소가 아닙니다

문제 정의

두 개의 숫자를 인자로 받아, 두 수가 서로소이면 true를, 그렇지 않으면 false를 반환하는 함수를 작성해야 합니다.

구현 방법

가장 간단한 접근 방식은 두 수 중 작은 값까지의 모든 숫자를 순회하면서, 두 수를 동시에 나눌 수 있는 값이 존재하는지 확인하는 것입니다. 만약 그런 값이 있다면 두 수는 서로소가 아닙니다.

아래는 이 로직을 구현한 코드입니다.

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));

코드 설명

• 먼저 삼항 연산자를 사용해 두 수 중 더 큰 값을 smaller 변수에 저장합니다.
• 2부터 시작하여 반복문을 돌면서 각 숫자가 두 수 모두의 약수인지 확인합니다.
• 두 조건(condition1, condition2)이 동시에 참이면 공통 약수가 존재한다는 뜻이므로 즉시 false를 반환합니다.
• 반복문이 끝날 때까지 공통 약수가 발견되지 않으면 두 수는 서로소이므로 true를 반환합니다.

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다.

true
true
true
false

앞의 세 쌍은 공통 소인수가 없어 true가 반환되었고, 마지막 21과 57은 공통 소인수 3을 가지고 있어 false가 반환된 것을 확인할 수 있습니다.