JavaScript에서 반복되는 소수 부분의 길이 찾기

문제

숫자 num을 첫 번째이자 유일한 인수로 받아 처리하는 JavaScript 함수를 작성해야 합니다.

이 함수는 다음 두 가지 작업을 수행해야 합니다.

먼저 입력된 숫자가 10과 서로소인지 확인합니다. 두 수의 공약수가 1뿐일 때 서로소라고 하는데, 서로소가 아니라면 -1을 반환합니다.
숫자가 10과 서로소라면, 1을 그 숫자로 나눴을 때 소수 부분에서 무한히 반복되는 자릿수의 길이를 반환합니다.

예를 들어 함수에 다음 값을 입력했다고 가정해 보겠습니다.

입력

const num = 123;

출력

const output = 5;

출력 설명

123은 2나 5를 약수로 가지지 않으므로 10과 서로소입니다.

1을 123으로 나누면 다음과 같습니다.

1 / 123 = 0.008130081300813…

소수 부분에서 00813이 무한히 반복되며 그 길이는 5이므로, 최종 출력값은 5가 됩니다.

예제 코드

다음은 위 문제를 해결하는 코드입니다.

const num = 123;
const findRepeatingPart = (num = 1) => {
    if(num % 2 === 0 || num % 5 === 0){
        return -1;
    } else {
        let res = 10 % num, count = 1;
        while(res != 1){
            res = res * 10 % num;
            count++;
        };
        return count;
    }
};
console.log(findRepeatingPart(num));

코드 작동 방식

어떤 수가 10과 서로소가 아니라는 것은 그 수가 2 또는 5의 배수라는 의미와 같습니다. 따라서 num % 2 === 0 또는 num % 5 === 0 조건만으로 서로소 여부를 간단히 판별할 수 있습니다.

서로소인 경우에는 나머지 연산을 활용해 반복 주기를 구합니다. 10 % num에서 시작하여 매번 현재 값에 10을 곱한 뒤 num으로 나눈 나머지를 대입하고, 나머지가 다시 1로 돌아올 때까지 반복 횟수를 셉니다. 이 횟수가 곧 반복되는 소수 부분의 길이입니다. 이는 1/n의 순환마디 길이가 10의 법 n에 대한 곱셈 위수(order)와 같다는 수학적 성질을 이용한 방법입니다.