[boj 9020] 골드바흐의 추측 - js

문제

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의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다.

출력

각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.

// 골드바흐의 추측

let fs = require('fs');
// let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n').map(Number); // 제출용
let input = fs.readFileSync('input.txt').toString().trim().split('\n').map(Number); // vscode 테스트용

const T = input.shift();
const arr = [...input];
const sol = (T,arr) =>{
    const resultArr = [];
    for(let i =0; i<arr.length; i++){
        const n = arr[i] // 주어진 n
        const nPrimeArr = isPrime(n); // n까지의 소수
        const primeNumArr = [];

        for(let j = 0; j<nPrimeArr.length; j++){
            if(nPrimeArr[j]) primeNumArr.push(j);
        }

        let tempArr = [];
        for(let j = 0; j<primeNumArr.length; j++){
            let difference = 10000;
            for(let k = j; k<primeNumArr.length; k++){
                if(primeNumArr[j] + primeNumArr[k] == n){
                    if(difference > Math.abs(primeNumArr[j]-primeNumArr[k])){
                        difference = Math.abs(primeNumArr[j]-primeNumArr[k]);
                        tempArr = [primeNumArr[j], primeNumArr[k]];
                    }
                }
            }
        }
        resultArr.push(tempArr);
    }

    for (const result of resultArr) {
        console.log(result[0], result[1]);
    }
}

const isPrime = (num) =>{
    const nPrimeArr = new Array(num+1).fill(true);
    nPrimeArr.splice(0,2,false,false);
    for(let i = 2; i<= Math.sqrt(num); i++){
        if(nPrimeArr[i]){
            for(let j = i*i; j<=num; j+=i){
                nPrimeArr[j] = false;
            }
        }
    }

    return nPrimeArr;
}

sol(T,arr);

풀이

1. 주어진 n 까지의 소수를 구한다.

2. n까지의 소수를 꺼내 차례로 더하며 값이 같은지 비교한다.

3. 값이 같은 값들 중 차이가 가장 적은 값을 결과 배열에 넣는다.

 

느낀점

머리로는 다 풀었는데 구현하는데에 생각보다 오래걸렸다. 구현에 좀 더 익숙해져야겠다 연습하자!