k-소수(K-Prime Number)란?
자연수가 정확히 k개의 소인수를 가질 때, 그 수를 k-소수(k-prime)라고 부릅니다. 여기서 중요한 점은 소인수를 세는 방식입니다. 같은 소수라도 곱해진 횟수만큼 중복해서 계산하며, 이를 '중복을 포함하여 계산(counted with multiplicity)'한다고 표현합니다.
예를 들어 4의 유일한 소인수는 2지만, 4 = 2 × 2이므로 2가 두 번 등장합니다. 따라서 4는 2-소수입니다.
마찬가지로 8 = 2 × 2 × 2이므로 소인수가 세 번 나타나며, 8은 3-소수입니다.
참고로 일반적인 소수(prime number)는 소인수가 하나뿐이므로 1-소수에 해당하고, 30 = 2 × 3 × 5처럼 서로 다른 세 소수의 곱으로 이루어진 수 역시 3-소수가 됩니다.
문제 정의
숫자 k, 거리(step), 그리고 범위(range)를 입력받는 JavaScript 함수를 작성해야 합니다.
함수는 주어진 범위 안에서 서로 간의 거리가 정확히 step과 일치하는 k-소수 쌍(pair)을 찾아, 배열의 배열 형태로 반환해야 합니다.
예를 들어 k = 2, step = 2, 범위가 [0, 50]이라면, 범위 내에서 두 수 모두 2-소수이면서 차이가 정확히 2인 숫자 쌍들을 모두 찾아야 합니다.
구현 예제
다음은 위 문제를 해결하는 전체 코드입니다.
const k = 2;
const step = 2;
const range = [0, 50];
const kPrimeSteps = (k = 1, step = 1, [start, end]) => {
const res = [];
let i = start;
const findLen = (n = 1) => {
let count = 0, i = 2;
while (i * i <= n) {
while (n % i === 0) {
count++;
n /= i;
}
i++;
}
if (n > 1) count++;
return count;
}
while (i <= end - step) {
if ((findLen(i) == k && findLen(i+step) == k))
res.push([i, i+step]);
i++;
}
return res;
};
console.log(kPrimeSteps(k, step, range));코드 동작 원리
핵심 로직은 크게 두 부분으로 나눌 수 있습니다.
① findLen 함수 — 소인수 개수 계산: 2부터 시작해 √n까지 반복하면서 n을 나눌 수 있는 만큼 나누고, 나눌 때마다 카운트를 증가시킵니다. 루프가 끝난 후 n이 1보다 크면 남은 값 자체가 소수이므로 카운트를 하나 더 올립니다. 이렇게 하면 중복을 포함한 소인수의 총 개수를 구할 수 있습니다.
② kPrimeSteps 함수 — 조건에 맞는 쌍 탐색: start부터 end - step까지 순회하면서 현재 수 i와 i + step이 모두 k-소수인지 확인합니다. 두 조건을 모두 만족하면 [i, i + step] 쌍을 결과 배열에 추가합니다.
출력 결과
다음은 콘솔 출력 결과입니다.
[ [ 4, 6 ], [ 33, 35 ] ]
결과를 해석해 보면 다음과 같습니다.
- [4, 6]: 4 = 2 × 2 (2-소수), 6 = 2 × 3 (2-소수)이며, 두 수의 차이는 정확히 2입니다.
- [33, 35]: 33 = 3 × 11 (2-소수), 35 = 5 × 7 (2-소수)이며, 마찬가지로 차이가 2입니다.
범위 [0, 50] 안에서 이 두 쌍만 조건을 모두 충족하기 때문에 최종적으로 두 개의 배열이 반환됩니다.