[백준] 콜드바흐의 추측 6588

🤖 문제

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

---

  1. 문제 내용

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

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

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

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

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

 

  2. 예제 및 출력

8
20
42
0

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

 

🤖 내가 풀은 방식에 필요한 지식

---

1.  Math.max

Math.max 함수 이전에 정리한 게시글 참고

[백준] 세로읽기 10798

 

2.  콜드바흐의 추측

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

출처 : 위키백과 - 골드바흐의 추측

 

 

3. 콜드바흐 파티션

짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 하며 아래와 같음.

4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 5 + 5
12 = 5 + 7
14 = 3 + 11
14 = 7 + 7

 

 

4. 에라토스테네스의 체

아래 정리 글 참고!

[알고리즘] 에라토스테네스의 체

 

 

🤖 풀이 및 코드

---

1. 전체 풀이 코드

1) 최댓값 찾기

 

const findMax = Math.max(...input);

• 입력된 수 중에서 최대값을 찾아 변수 findMax에 저장

 

 

2) 에라토스테네스의 체를 이용한 소수 판별

 

const arr = Array.from({ length: findMax + 1 }).fill(true);

• 배열 arr을 생성하고 초기값을 true로 설정합니다. 인덱스 0과 1은 소수가 아니므로 false로 변경합니다.
• 제곱근까지만 반복하면서 각 소수의 배수를 false로 변경하여 소수를 판별

 

 

3) 콜드바흐의 추측 확인

 

input.map((x) => { ... });

• 각 입력된 수 x에 대해 짝수는 골드바흐의 추측을 만족하는 두 소수로 나타낼 수 있습니다.

for (let i = 3; i < x; i += 2):

• 홀수인 경우에 대해서만 반복하여 첫 번째 소수 i를 선택하고, x - i가 소수인지 확인하여 출력

 

 

const input = require('fs').readFileSync(process.platform === "linux" ? "/dev/stdin" : "../input.txt").toString().trim().split("\n").map(Number);

const findMax = Math.max(...input);
const arr = Array.from({ length: findMax + 1 }).fill(true);
arr[0] = arr[1] = false;
const sqrt = parseInt(Math.sqrt(findMax));

for (let i = 2; i <= sqrt; i++) {
  if (arr[i] === true) {
    for (let j = 2; i * j <= findMax; j++) {
      arr[i * j] = false;
    }
  }
}

let result = "";
input.map((x) => {
  for (let i = 3; i < x; i += 2) {
    if (arr[i] && arr[x - i]) {
      result += `${x} = ${i} + ${x - i}\n`;
      break;
    }
  }
});
console.log(result);

 

---

콜드바흐의 추측 문제를 풀 때도 에라토스테네스의 체 개념이 필요했따..!
돌고 도는구만!