[백준 | Javascript] 9020

기본 수학2. 6단계
9020번. 골드바흐의 추측

문제

9020번 문제 링크

solution

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

const iter = input[0];

// 1. num에서 가장 작은 소수를 뺌
// 2. 남은 숫자가 소수인지 판별
// 3. 소수가 맞다면 경우의 수에 추가, 소수가 아니라면 1번에서 다음 소수로 반복
// 4. 모든 경우의 수를 얻었으면
// 5. 차이가 가장 작은 것을 출력

for(let i = 1; i <= iter; i++){
  const num = input[i];
  
  let prime = [];
  
  // 2 ~ num-1 까지의 숫자 중 소수만 추출
  outer: for(let j = 2; j < num; j++){
	inner: for(let k = 2; k*k <= j; k++){
      // j가 k로 나누어떨어지면 소수가 아니므로 outer 반복문을 continue
      if(j % k === 0){
        continue outer;
      }
    }
    // 위 조건을 통과했다면 해당 j는 소수이므로 prime 배열에 추가
    prime.push(j);
  }
  
  // 골드바흐 파티션이 될 수 있는 것들을 넣기 위한 빈 배열
  let partitionArr = [];
  
  // num에서 가장 작은 소수를 뺄셈
  for(let n = 0; n < prime.length; n++){
    // num에서 처음으로 빼줄 소수
    let first = prime[n];
    
    // num에서 first를 뺀 수가 소수인지 판별해야함
    let second = num - first;
    
    // 만약 prime 배열에 second가 없다면
    // second는 소수가 아니므로 다음 prime[n]을 first에 넣어서 반복
   	if(!prime.includes(second)) {
      continue;
    }
    
    // 만약 위 조건을 통과하면 second는 소수이므로
    // first와 second는 골드바흐 파티션이 될 수 있다.
    const partition = { first: first, second: second, gap: second - first };
    
    // 주의 할 점! 예를들어 num = 8 일 때,
    // 3,5와 5,3이 나올 수 있다.
    // gap을 계산하면 5,3이 더 작게 나오게 된다.(음수가 되어버리므로)
    // 우리는 3,5 순서로 출력하고싶기 때문에 굳이 같은 값들을 원소로 가지는 파티션들은
    // 또 한번 계산할 필요가 없다.(오히려 원하는 출력에 방해가 되므로)
    // 그래서, gap이 음수인 것들은 partition에 포함시키지 않겠다.
    // 이렇게 하면 2,2처럼 차이가 0이 되는 파티션도 포함시킬 수 있다.
    if(partition.gap < 0){
      continue;
    }
    
    partitionArr.push(partition);
  }
  
  // partitionArr 중 gap이 가장 작은 것을 찾아서 first와 second를 출력
  // partitionArr를 오름차순 정렬
  const result = partitionArr.sort((a, b) => {
    return a.gap - b.gap;
  })
  
  // result의 첫번째 원소가 gap이 가장 작은 것이므로
  // 그 때의 first와 second를 출력
  console.log(`${result[0].first} ${result[0].second}`); 
}