JavaScript로 범위 내 자릿수 제곱의 합이 1에 도달하는 소수 개수 구하기

문제 이해하기

두 개의 숫자로 이루어진 범위 배열을 인수로 받는 JavaScript 함수를 작성해야 합니다. 함수는 해당 범위 안에서, 각 자릿수를 제곱해 더하는 과정을 반복했을 때 최종적으로 1에 도달하는 소수의 개수를 반환해야 합니다.

예를 들어 23은 소수이며, 다음 과정을 거쳐 1에 도달합니다.

2² + 3² = 13
1² + 3² = 10
1² + 0² = 1

따라서 23은 조건을 만족하는 유효한 숫자입니다. 이렇게 자릿수 제곱의 합을 반복 계산했을 때 1에 도달하는 수는 흔히 행복한 수(happy number)라고 부르며, 이번 문제에서 구해야 하는 것은 바로 이러한 성질을 가진 소수, 즉 행복한 소수(happy prime)입니다.

접근 방법

문제를 해결하려면 다음 두 가지 하위 문제를 각각 처리해야 합니다.

소수 판별 — 주어진 수가 소수인지 확인합니다. 2와 3을 먼저 처리한 뒤 6k±1 꼴의 약수 후보만 검사하면 효율적입니다.
수열 추적 — 각 자릿수 제곱의 합을 계속 구하다가, 이미 나왔던 수가 다시 등장하면 사이클에 빠진 것이므로 1에 도달하지 못합니다. 이때 반복을 중단하고 실패로 처리합니다.

범위 내 모든 수에 대해 두 조건을 동시에 만족하는지만 검사한 뒤, 만족하는 수의 개수를 세면 됩니다.

구현 코드

const range = [2, 212];
String.prototype.reduce = Array.prototype.reduce;
const isPrime = (n) => {
    if ( n<2 ) return false;
    if ( n%2===0 ) return n===2;
    if ( n%3===0 ) return n===3;
    for ( let i=5; i*i<=n; i+=4 ) {
        if ( n%i===0 ) return false;
        i+=2;
        if ( n%i===0 ) return false;
    }
    return true;
}
const desiredSeq = (n) => {
    let t=[n];
    while ( t.indexOf(n)===t.length-1 && n!==1 )
    t.push(n=Number(String(n).reduce( (acc,v) => acc+v*v, 0 )));
    return n===1;
}
const countDesiredPrimes = ([a, b]) => {
    let res=0;
    for ( ; a<b; a++ )
        if ( isPrime(a) && desiredSeq(a) )
        res++;
    return res;
}
console.log(countDesiredPrimes(range));

코드 설명

isPrime: 2와 3으로 나누어떨어지는 경우를 먼저 걸러내고, 이후에는 6k±1 형태의 수만 검사해 소수 여부를 판별합니다.
desiredSeq: 자릿수 제곱의 합을 반복 계산하면서 지금까지 등장한 수를 배열 t에 기록합니다. 새로 계산된 수가 이미 배열에 있다면 사이클이 발생한 것이므로 반복을 멈추고, 최종 값이 1인지를 반환합니다.
String.prototype.reduce = Array.prototype.reduce: 배열의 reduce 메서드를 문자열에 빌려 쓰는 기법으로, 문자열의 각 자릿수 문자에 접근해 제곱합을 손쉽게 계산할 수 있습니다.
countDesiredPrimes: 범위 [a, b)의 모든 수를 순회하며 소수이면서 수열이 1로 끝나는 경우만 골라 개수를 더합니다.

실행 결과

범위 [2, 212]에 대해 위 코드를 실행하면 아래와 같은 결과가 출력됩니다.

즉, 2 이상 212 미만 범위에는 조건을 만족하는 소수가 총 12개 있으며, 실제로는 7, 13, 19, 23, 31, 79, 97, 103, 109, 139, 167, 193입니다.