JavaScript로 배열의 모든 숫자를 나눌 수 있는 가장 작은 수 찾기

숫자 배열을 입력받아, 배열 안의 모든 숫자를 나머지 없이 정확히 나눌 수 있는 수를 반환하는 JavaScript 함수를 작성해야 하는 경우가 있습니다. 이 문제는 각 숫자의 약수를 구한 뒤, 모든 요소에 공통으로 존재하는 약수만 추리는 방식으로 해결할 수 있습니다.

문제 해결 접근 방식

핵심 아이디어는 다음과 같습니다.

배열의 각 숫자에 대해 1보다 큰 약수 목록을 만듭니다.
첫 번째 숫자의 약수 목록을 기준으로 삼고, 이후 숫자들의 약수 목록과 교집합을 구합니다.
마지막까지 남은 값들이 바로 모든 숫자를 나눌 수 있는 공통 약수입니다.

예제 코드

위 로직을 구현한 코드는 다음과 같습니다.

const arr = [4, 6, 34, 76, 78, 44, 34, 26, 88, 76, 42];

const dividesAll = el => {
    const result = [];
    let num;
    // 자기 자신의 절반부터 2까지 내려가며 약수를 찾음
    for (num = Math.floor(el / 2); num > 1; num--) {
        if (el % num === 0) {
            result.push(num);
        }
    }
    return result;
};

const dividesArray = arr => {
    // 각 숫자의 약수 목록을 만든 뒤 교집합만 남김
    return arr.map(dividesAll).reduce((acc, val) => {
        return acc.filter(el => val.includes(el));
    });
};

console.log(dividesArray(arr));

실행 결과

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

[ 2 ]

즉, 배열의 모든 숫자를 나눌 수 있는 수는 2뿐이며, 따라서 가장 작은 공통 약수도 2입니다.

코드 동작 원리

dividesAll: 하나의 숫자를 받아, 그 숫자의 절반(floor(el / 2))부터 2까지 역순으로 검사하며 나누어떨어지는 값을 배열에 담아 반환합니다.
dividesArray: map()으로 배열 전체의 약수 목록을 만들고, reduce()와 filter(), includes()를 조합해 교집합을 단계적으로 계산합니다.

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

위 방식은 각 숫자마다 반복문을 돌기 때문에 숫자가 커지면 성능이 떨어질 수 있습니다. 유클리드 호제법으로 최대공약수(GCD)를 구하면 훨씬 간결하고 빠르게 해결할 수 있습니다.

const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));

const arr = [4, 6, 34, 76, 78, 44, 34, 26, 88, 76, 42];
const smallestDivisor = arr.reduce((acc, val) => gcd(acc, val));

console.log(smallestDivisor); // 2

배열 전체의 최대공약수가 곧 모든 숫자를 나눌 수 있는 가장 큰 수이며, 공통 약수들은 항상 이 값의 약수이므로 결과를 손쉽게 도출할 수 있습니다. 실무에서는 성능과 가독성 면에서 GCD 방식을 사용하는 것이 좋습니다.