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

문제 번호

9020번: 골드바흐의 추측

 

 

 

알고리즘 분류

• 수학
• 정수론
• 소수 판정
• 에라토스테네스의 체

 

문제 풀이

 짝수를 두개의 소수로 나타내는 문제이다. 문제에서 주어진 입력의 범위가 10000 이하 이기때문에 prime 이라는 배열을 만들어서 10000 이하의 소수들을 모두 저장해주었다. 에라토스테네스의 체 만드는거랑 같다고 생각한다.

function makePrime() {
  for (let i = 2; i <= 10000; i++) {
    let isPrime = true;
    for (let j = 2; j <= Math.sqrt(i); j++) {
      if (i % j === 0) {
        isPrime = false;
        break;
      }
    }
    if (isPrime)
      prime.push(i);
  }
}

 이제는 만들어진 prime 배열에서 2개씩 짝지어보면서 입력으로 주어진 n을 만들어보면된다. n을 만들 수 있는 경우가 여러가지라면 소수들의 차가 가장 적은것을 선택하라 했으므로 모든 소수들을 모두 더해본뒤 조건에 맞는 소수들을 선택한다. 나는 그냥 브루트포스로 검색했는데 이분탐색으로 하면 더 금방 찾을 수 있을것같다.

while (TC--) {
    let n = +input[testcase++];
    let diff = Infinity;
    let a, b;

    for (let i = 0; i < prime.length; i++) {
      let sum = prime[i];
      for (let j = i; j < prime.length; j++) {
        if (sum + prime[j] > n) break;
        if (sum + prime[j] === n) {
          if (prime[j] - prime[i] < diff) {
            a = prime[i];
            b = prime[j];
          }
        }
      }
    }
    answer += `${a} ${b}\n`;
  }
  return answer;

 

전체코드

const input = require('fs').readFileSync('input.txt').toString().split('\n');
let TC = +input[0];
let prime = [];

console.log(sol(TC).trim());

function sol(TC) {
  let answer = '';

  let testcase = 1;
  makePrime();

  while (TC--) {
    let n = +input[testcase++];
    let diff = Infinity;
    let a, b;

    for (let i = 0; i < prime.length; i++) {
      let sum = prime[i];
      for (let j = i; j < prime.length; j++) {
        if (sum + prime[j] > n) break;
        if (sum + prime[j] === n) {
          if (prime[j] - prime[i] < diff) {
            a = prime[i];
            b = prime[j];
          }
        }
      }
    }
    answer += `${a} ${b}\n`;
  }
  return answer;
}

function makePrime() {
  for (let i = 2; i <= 10000; i++) {
    let isPrime = true;
    for (let j = 2; j <= Math.sqrt(i); j++) {
      if (i % j === 0) {
        isPrime = false;
        break;
      }
    }
    if (isPrime)
      prime.push(i);
  }
}

특이사항