제코베 JS 100제 / 69 / 골드바흐의 추측

골드바흐의 추측(Goldbach's conjecture)은 오래전부터 알려진 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 개의 소수(Prime number)의 합으로 표시할 수 있다는 것이다. 이때 하나의 소수를 두 번 사용하는 것은 허용한다. - 위키백과

 

위 설명에서 2보다 큰 모든 짝수를 두 소스의 합으로 나타낸 것을 골드바흐 파티션이라고 합니다.

 

예)

100 == 47 + 53

56 == 19 + 37

 

2보다 큰 짝수 n이 주어졌을 때, 골드바흐 파티션을 출력하는 코드를 작성하세요.

 

* 해당 문제의 출력 형식은 자유롭습니다. 가능하시다면 골드바흐 파티션 모두를 출력하거나, 그 차가 작은 것을 출력하거나 그 차가 큰 것 모두 출력해보세요.

 

/**
 * n까지의 인덱스를 가진 배열에서 n이 소수라면 true, 아니라면 false를 해주고
 *
 * 그 배열을 리턴해주는 함수
 * @param {Number} n 2보다 큰 짝수
 * @param {Boolean[]} arr true로 초기화된 n의 길이를 가진 배열
 * @returns {Boolean[]} n의 길이를 가진 각 인덱스가 소수인지 아닌지 판별 완료된 배열
 */
function isPrime(n, arr) {
  for (let i = 2; i * i <= n; i++) {
    if (arr[i] === true) {
      for (let j = i * 2; j <= n; j += i) {
        arr[j] = false;
      }
    }
  }

  return arr;
}
/**
 * 모든 골드바흐 파티션을 출력해주는 함수
 * @param {Number} n 2보다 큰 짝수
 * @param {Boolean[]} prime_arr n의 길이를 가진 각 인덱스가 소수인지 아닌지 판별 완료된 배열
 */
function printAllGoldbach(n, prime_arr) {
  for (let i = 2; i <= n; i++) {
    for (let j = 2; j <= n; j++) {
      if (prime_arr[i] && prime_arr[j] && i + j === n) {
        console.log(`${i + j} == ${i} + ${j}`);
      }
    }
  }
}

/**
 * 가장 차이가 작은 골드바흐 파티션을 출력해주는 함수
 * @param {Number} n 2보다 큰 짝수
 * @param {Boolean[]} prime_arr n의 길이를 가진 각 인덱스가 소수인지 아닌지 판별 완료된 배열
 */
function printMinDistanceGoldbach(n, prime_arr) {
  for (let i = 2; i <= n; i++) {
    for (let j = 2; j <= n; j++) {
      if (prime_arr[i] && prime_arr[j] && i + j === n) {
        if (i >= j) {
          console.log(`${i + j} == ${j} + ${i}`);
          console.log(`${i + j} == ${i} + ${j}`);
          return;
        }
      }
    }
  }
}

/**
 * 가장 차이가 큰 골드바흐 파티션을 출력해주는 함수
 * @param {Number} n 2보다 큰 짝수
 * @param {Boolean[]} prime_arr n의 길이를 가진 각 인덱스가 소수인지 아닌지 판별 완료된 배열
 */
function printMaxDistanceGoldbach(n, prime_arr) {
  for (let i = 2; i <= n; i++) {
    for (let j = 2; j <= n; j++) {
      if (prime_arr[i] && prime_arr[j] && i + j === n) {
        console.log(`${i + j} == ${i} + ${j}`);
        console.log(`${i + j} == ${j} + ${i}`);
        return;
      }
    }
  }
}

function solution(n) {
  let prime_arr = Array.from({ length: n }, () => true);
  prime_arr[0] = prime_arr[1] = false;

  prime_arr = isPrime(n, prime_arr);

  printAllGoldbach(n, prime_arr);
  console.log("---------------------------------------");
  printMinDistanceGoldbach(n, prime_arr);
  console.log("---------------------------------------");
  printMaxDistanceGoldbach(n, prime_arr);
}

const n = 100;
solution(n);

---

소수를 구하는 방식은 '에라토스테네스의 체' 알고리즘을 사용하였다. (이전에 따로 정리한 아래 포스팅 참조)

2022.01.16 - [ALGORITHM/etc] - 에라토스테네스의 체

에라토스테네스의 체

 

따라서 소수 배열을 구했다면, 두 소수의 합이 주어진 수인지만 판단하여 출력해주면 된다.

 

단, 가장 차가 작은 골드바흐 파티션을 구할 때의 방법을 특이하게 했는데,

만약 문제에서 주어진대로 100의 모든 골드바흐 파티션을 구하게 된다면

 

...

100 == 47 + 53

100 == 53 + 47

...

 

위와 같이 될것이다.

 

따라서 골드바흐 파티션은 중심으로 대칭을 이루는 구조이다.

가능한 모든 골드바흐 파티션을 나열했을 때, 중심에 가까울수록 그 차가 적다는것을 알 수 있다.

따라서 첫번째 수가 두번째 수보다 커지는 순간이 대칭수가 되는것이므로 그때의 조건을 달아주어 구했다.

 

차가 제일 큰 경우는 맨 처음과 맨 마지막이므로 맨 처음의 골드바흐 파티션만 구해서 위치를 바꿔주어

똑같이 대칭수를 출력해주면 된다.