[백준] 6588. 골드바흐의 추측 풀이 / Python, JavaScript

6588번: 골드바흐의 추측

 

작성 코드 (.py)

import sys
sys.stdin = open("input.txt", "r") # 제거
input = sys.stdin.readline

n = 1000001
# 소수 아닌 모든 홀수 처리
table = [1] * n
for i in range(3, int(n ** 0.5) + 1, 2):
    if table[i]:
        for j in range(i * 2, n, i):
            table[j] = 0
# k가 만들어지는 두 홀수인 소수 검색
while 1:
    k = int(input())
    if not k:
        break
    for i in range(3, int(k / 2) + 1, 2):
        if table[i] and table[k - i]:
            print(f"{k} = {i} + {k - i}")
            break
    else:
        print("Goldbach's conjecture is wrong.")

작성 코드 (.js)

function solution(numbers) {
  const n = 1000001;
  // 소수 아닌 모든 홀수 처리
  const table = Array(n).fill(1);
  for (let i = 3; i <= parseInt(n ** 0.5); i += 2) {
    if (table[i]) {
      for (let j = i * 2; j < n; j += i) table[j] = 0;
    }
  }
  const result = [];
  // k가 만들어지는 두 홀수인 소수 검색
  for (const k of numbers) {
    if (!k) break;
    let exist = false;
    for (let i = 3; i <= parseInt(k / 2); i += 2) {
      if (table[i] && table[k - i]) {
        result.push(`${k} = ${i} + ${k - i}`);
        exist = true;
        break;
      }
    }
    if (!exist) result.push("Goldbach's conjecture is wrong.");
  }
  return result;
}
console.log(solution([8, 20, 42, 0]));

 

구현 알고리즘 (에라토스테네스의 체)

이 문제의 핵심은 <4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다>라는 편지의 내용입니다. 이 부분을 효율적으로 구현하지 않았다면 100% 제한 시간에 걸릴겁니다. 에라토스테네스의 체를 구현할 때 모든 소수를 찾아줄 필요가 없습니다. 홀수의 합이라고 하였으니 홀수인 소수만 판별해준 테이블을 사용하면 되겠습니다.

 

입력값 k가 만들어지는 두 홀수인 소수를 검색하기 위해서는 가장 작은 소수인 3부터 2칸씩 건너뛰며 테이블에 현재 i값이 소수인지와 k - i값이 소수인지를 확인하면 됩니다. 검색 코드의 두번째 for문 역시 모든 수를 확인해줄 필요없이 k의 절반까지만 확인합니다. 문제의 조건에서는 만족하는 결과가 여러개일 경우 차가 가장 큰 것을 사용하라고 했지만 어차피 처음 발견되는 것이 가장 차가 큰 수들이므로 발견되면 즉시 i값과 k - i값을 결괏값에 입력해줍니다.