[JS]백준 9020번 골드바흐의 추측

출처

https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

문제

1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

풀이

이 문제 역시 소수 판별식을 이용하여 쉽게 해결할 수 있었다. 나는 input을 각각 돌면서 그 숫자들보다 작은 소수들을 primeArr에 집어넣었다. 이후 주어진 숫자에서 소수를 각각 빼면서 만약 그 수가 소수라면 골드바흐 파티션이므로 그 두 수의 조합을 ans에 배열로 넣어 주었는데, 골드바흐 파티션을 지켜보니 3 5 5 3이런식으로 중복이 되는 것을 확인할 수 있었다.
따라서 중복을 피하기 위해 소수가 input의 절반보다 작을 때까지만 그 경우를 반복하도록 하였다. 그러면 ans에 골드바흐 파티션들이 출력된 배열이 들어가는데, 그중에 가장 마지막 값이 소수의 차이가 가장 작은 것이므로 마지막 값에 접근을 하여 정답을 출력하였다.

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n').map(Number);
const test = input[0];
const isPrime = (n) => {
    if (n == 1) {
      return false;
    }
    for (let i = 2; i <= Math.sqrt(n); i++) {
      if (n % i === 0) {
        return false;
      }
    }
    return true;
}
for (i = 1; i <= test; i++) {
    let num = input[i];
    let primeArr = [];
    for (j = 2; j < num; j++) {
        if (isPrime(j)) {
            primeArr.push(j);
        }
    }
    let ans = [];
    for (k = 0; primeArr[k] < num / 2 + 1; k++) {
        if (isPrime(num - primeArr[k])) {
            ans.push([primeArr[k], num - primeArr[k]]);
        }
    }
    let a = ans.pop();
    console.log(`${a[0]} ${a[1]}`);
}

에라토스테네스의 체

추가로, 소수를 구할때 가장 최단시간으로 구할 수 있는 알고리즘을 알게 되었는데 바로 "에라토스테네스의 체" 이다. 이 알고리즘의 원리는 주어진 수가 1~100이라면 2를제외한 2의배수를 지우고, 3을제외한 3의배수를 지우고 이렇게 쭉쭉 지워나가면 소수만 남게 되는 것이다.
예제코드

const n = 2;
const m = 10000;
let primeArr = [];
for (i = n; i <= m; i++) {
    primeArr[i] = i;
}
for (i = n; i <= m; i++) {
    if (primeArr[i] === 0) continue;
    for (j = i + i; j <= m; j += i) {
        primeArr[j] = 0;
    }
}