[백준] 6588번 node.js 풀이, 골드바흐의 추측: 3트 과정 기록

문제 설명

링크

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

문제

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.

이 추측은 아직도 해결되지 않은 문제이다.

백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

 

 

입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.

각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)

입력의 마지막 줄에는 0이 하나 주어진다.

 

출력

 

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

 

예제입력

8
20
42
0

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

문제 풀이

총 3번 트라이했는데 그 과정을 담아보겠다.

 

1트) 시간초과로 실패 

짝수를 구성하는 홀수 a, b를 반복문을 돌며 소수를 판별하는 함수에 넣는다.

• 두 홀수가 모두 소수인 경우 -> 출력 형식 때로 출력
• 반복문 도는 동안 둘 다 소수인 경우가 없다면 에러메시지 출력
• 이때 소수 판별은 제곱근보다 적은 홀수까지만 검사해도 된다. -> 참고 블로그 글 https://velog.io/@changhee09/알고리즘-소수의-판별-에라토스테네스의-체
• 왜냐하면 약수를 구할 때, 대칭이기 때문이다.

const fs = require('fs');
const input = fs
  .readFileSync(
    process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt'
  )
  .toString()
  .trim()
  .split('\n')
  .map(Number);
const error_message = "Goldbach's conjecture is wrong.";

//소수 판별 함수
function isPrimeNumber(num) {
  //제곱근보다 낮은 홀수로만 나눠보기
  for (let i = 3; i <= parseInt(Math.sqrt(num)); i += 2) {
    if (num % i === 0) return false;
  }
  return true;
}

let idx = 0;
while (input[idx] !== 0) {
  const num = input[idx];
  let check = false; //해당 짝수가 두 소수의 합으로 이뤄지는게 있는지 확인.
  for (let i = num - 3; i >= num / 2; i -= 2) {
    if (isPrimeNumber(num - i) && isPrimeNumber(i)) {
      console.log(`${num} = ${num - i} + ${i}`);
      check = true;
      break;
    }
  }
  idx += 1;
  if (!check) {
    console.log(error_message);
  }
}

 

 

2트) 소수를 미리 구해놓기.

소수를 그때그때 함수로 검사한다면 조회 횟수가 많아 계산이 느리다.
테스트케이스가 100,000건인 경우 어마무시한 시간비용이 난다. 따라서 소수를 미리 구해놓는다. 

n의 최대는  1,000,000으로, 이 안에서 홀수인 소수를 모아둔 배열을 만드다.

 

const fs = require('fs');
const input = fs
  .readFileSync(
    process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt'
  )
  .toString()
  .trim()
  .split('\n')
  .map(Number);
const error_message = "Goldbach's conjecture is wrong.";

//소수면 false
const arr = Array.from({ length: 1000001 }, () => 1); //길이가 1000000인 0인 배열 생성
for (let i = 3; i <= 499999; i += 2) {
  if (arr[i]) {
    for (let j = 3; i * j <= 1000001; j += 2) {
      //배수삭제
      arr[i * j] = 0;
    }
  }
}

let idx = 0;
while (input[idx] !== 0) {
  const num = input[idx];
  let check = false; //해당 짝수가 두 소수의 합으로 이뤄지는게 있는지 확인.
  for (let i = num - 3; i >= num / 2; i -= 2) {
    if (arr[i] && arr[num - i]) {
      console.log(`${num} = ${num - i} + ${i}`);
      check = true;
      break;
    }
  }
  idx += 1;
  if (!check) {
    console.log(error_message);
  }
}

 

 

이것도 시간초과..

 

 

3트) console.log 출력이 많으면 그만큼 비용이 많이발생하므로 출력비용을 줄이자

배열에 출력할 걸 모아두고 join('\n')을 이용해 출력을 한번에 한다.

const fs = require('fs');
const input = fs
  .readFileSync(
    process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt'
  )
  .toString()
  .trim()
  .split('\n')
  .map(Number);
const error_message = "Goldbach's conjecture is wrong.";

//소수면 false
const arr = Array.from({ length: 1000001 }, () => 1); //길이가 1000000인 0인 배열 생성
for (let i = 3; i <= 499999; i += 2) {
  if (arr[i]) {
    for (let j = 3; i * j <= 1000001; j += 2) {
      arr[i * j] = 0;
    }
  }
}

const answer = [];
let idx = 0;
while (input[idx] !== 0) {
  const num = input[idx];
  let check = false; //해당 짝수가 두 소수의 합으로 이뤄지는게 있는지 확인.
  for (let i = 3; i <= num / 2; i += 2) {
    if (arr[i] && arr[num - i]) {
      answer.push(`${num} = ${i} + ${num - i}`);
      check = true;
      break;
    }
  }
  idx += 1;
  if (!check) {
    answer.push(error_message);
  }
}

console.log(answer.join('\n'));

 

 

이 문제를 통해 테스트케이스가 많다면, 정적으로 미리 경우의 수를 짜놓는 방식도 생각해야 됨을 알았다.

또, console.log의 출력 비용이 많이드니 join과 배열을 활용해 한번에 출력하도록 하는 방식도 알게되었다.