JavaScript로 합이 입력 숫자가 되는 모든 소수 쌍 찾기

문제

하나의 숫자 n을 매개변수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 두 수의 합이 정확히 n이 되고, 두 수가 모두 소수(prime)인 모든 숫자 쌍을 담은 배열을 반환해야 합니다.

예시

다음은 전체 코드입니다 −

const num = 26;
const isPrime = (n) => {
   if (n % 2 === 0) return false;
   let sqrtn = Math.sqrt(n)+1;
   for (let i=3; i < sqrtn; i+=2) {
      if (n % i === 0) return false;
   }
   return true;
}
const primeList = (a) => {
   if (isPrime(a)) return a; else return false;
};
const generateNumbers = (n) => {
   let num = (n % 2 === 0) ? (n -1) : n;
   let list = []
   for (let i = num; i > 3; i-=2)
      list.push(i);
   list.push(3,1);
   return list;
}
const calculate = (num, list, results) => {
   if (list.length === 0) return results;
      let item = list.shift();
   let itemPairIndex = list.indexOf(num - item);
   if (itemPairIndex !== -1) {
      let itemPair = list.splice(itemPairIndex,1)
      results.push(item+"+"+itemPair);
   }
   return calculate(num, list, results);
}
const findprimeSum = (num) => {
   const pairs = [];
   const list = generateNumbers(num).filter(primeList);
   return calculate(num, list, []);
}
console.log(findprimeSum(num));

코드 동작 원리

• isPrime(n): 짝수를 먼저 제외한 뒤, 3부터 √n+1까지 홀수만으로 나누어 소수 여부를 효율적으로 판별합니다.
• generateNumbers(n): n 이하의 홀수들(3과 1 포함)을 내림차순으로 담은 후보 목록을 생성합니다.
• primeList(a): filter 단계에서 사용되며, 목록에서 실제 소수인 값만 남기도록 합니다.
• calculate(num, list, results): 재귀 호출을 통해 목록에서 값을 하나씩 꺼내고, 그 값과 더했을 때 num이 되는 짝이 목록에 존재하면 두 값을 묶어 결과 배열에 추가합니다.

출력

[ '23+3', '19+7' ]

숫자 26을 입력하면 26 = 23 + 3 = 19 + 7이 성립하므로, 위와 같이 두 개의 소수 쌍이 결과로 반환됩니다.