알고리즘 기초 1/2. 300 - 수학1
6588번. 골드바흐의 추측

문제

6588번 문제 링크

solution

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map((item) => Number(item));

let ans = "";

const max = Math.max(...input);

// 주어진 input 중 가장 큰 수까지의 소수를 구해놓는다
let isPrime = new Array(max + 1).fill(true);

isPrime[0] = false;
isPrime[1] = false;

for(let i = 2; i*i < max; i++){
    if(isPrime[i]){
        let multiple = 2;
        
        while(i * multiple < max){
            isPrime[i * multiple] = false;
            multiple++;
        }
    }
}

// 소수 중 홀수만 가지고 진행해야하므로 2를 제외하고 진행한다.
// 따라서 0,1,2를 제외한 인덱스인 3부터 시작됨.
input.map((item) => {
    // input의 원소 값인 item까지의 범위 내에 있는 소수들만으로 판단.
    // 인덱스가 곧 소수값이기 때문에 가능한 풀이.
    for(let i = 3; i <= item; i++){
        // 예를들어, item이 8이라면 3 ~ 8 사이에 있는 소수만으로 표현을 해야된다.
        // i = 3이라면 item - i = 8 - 3 = 5가 된다.
        // 만약, 경우의 수가 여러가지가 나올 가능성이 있더라도
        // 가장 앞과 가장 끝 소수부터 시작해서 점점 좁혀가는 것이기 때문에, 가장 빨리 만족하는 두 수가 정답이 된다.
        if(isPrime[i] && isPrime[item - i]){
            ans += `${item} = ${i} + ${item - i}\n`;
            break;
        }
    }
});

console.log(ans);

시간 초과

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map((item) => Number(item));

const max = Math.max(...input);

// 주어진 input 중 가장 큰 수까지의 소수를 구해놓는다
let isPrime = new Array(max + 1).fill(true);

isPrime[0] = false;
isPrime[1] = false;

for(let i = 2; i*i < max; i++){
    if(isPrime[i]){
        let multiple = 2;
        
        while(i * multiple < max){
            isPrime[i * multiple] = false;
            multiple++;
        }
    }
}

// 소수만 넣어놓을 배열
let prime = [];

for(let i = 0; i < max; i++){
    if(isPrime[i]){
        prime.push(i);
    }
}

// 문제 진행
while(input[0] !== 0){
    let num = input.shift();
    
    let firsts = [];
    
    for(let i = 0; i < prime.length; i++){
        let first = prime[i];
        
        let seconds = [];
        
        for(let j = 0; j < prime.length; j++){
            let second = num - first;
            
            if(prime.includes(second)){
                seconds.push(second);
                firsts.push(first);
            }
        }
    }
    
    if(seconds.length === 0){
        console.log("Goldbach's conjecture is wrong.");
        
        continue;
    }
    
    let gaps = [];
    
    for(let i = 0; i < firsts.length; i++){
        let gap = seconds[i] - firsts[i];
        
        gaps.push(gap);
    }
    
    let maxGap = Math.max(...gaps);
    
    let index = gaps.indexOf(maxGap);
    
    console.log(`${num} = ${firsts[index]} + ${seconds[index]}`);
    
}

뭔가 의식의 흐름을 따라서 코드를 작성하다보니 엄청 길어졌다.
제출하면서 시간초과가 너무 뻔히 예상이 됐는데, 역시나 시간 초과다.
뭐가 문제였을까?
지금 보니 소수 중 홀수만 가져와야하는 것도 처리를 하지않았다.
소수는 2를 제외하고는 짝수가 없기 때문에 2만 제거하면 된다.

참고 자료

참고 자료 1
참고 자료 2