[boj] 6588. 골드바흐의 추측

[boj] 6588. 골드바흐의 추측

• 문제 링크 : https://www.acmicpc.net/problem/6588
• 사용 언어 : Node.js

6588번: 골드바흐의 추측

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

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

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

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

---

 

1. 문제 분석

 홀수인 소수들로 주어진 수를 만들 수 있는 경우가 존재하는지 확인하는 문제입니다.
일정 범위 내의 소수들을 구하고 그 수들을 통해 주어진 수를 도출해 보면 됩니다.
여러 개의 소수들을 구해야 하므로 시간 초과를 피하기 위해 에라토스테네스의 체를 활용하겠습니다.
에라토스테네스의 체에 대한 설명은 아래 링크로 첨부하겠습니다.

소수

 

---

 

2. 솔루션

const fs = require('fs')
const cases = fs.readFileSync(process.platform ===
                              'linux' ? '/dev/stdin' : 'input.txt').toString()
                .split('\n').map(n => +n.trim())
// 주어진 Case 들 중 가장 큰 수
const max = Math.max(...cases)
// 가장 큰 수만큼의 크기의 에라토스테네스의 체
const sieve = Array.from({
    length: max + 1
}, (val, index) => true)
sieve[0] = false;
sieve[1] = false;
// 체 생성하여 소수 구하기
for (let i = 2; i * i <= max; i++) {
    if (!sieve[i]) continue;
    for (let j = i * 2; j <= max; j += i) {
        sieve[j] = false;
    }
}

const answer = [];

for (let i = 0; i < cases.length; i++) {
    // 현재 테스트 케이스
    const sumOfPrimeNumber = cases[i];
    // '0'이 들어오면 테스트 종료
    if (sumOfPrimeNumber === 0) break;
    // 홀수 소수의 합을 발견했는지 여부
    let found = false;
    // 홀수 소수를 탐색 하기에 '3' 부터 탐색 시작
    for (let j = 3; j < sumOfPrimeNumber; j++) {
        // j 가 소수이고 (주어진 테스트 케이스 - j) 가 소수 이면 조건 부합
        if (sieve[j] && sieve[sumOfPrimeNumber - j]) {
            answer.push(`${sumOfPrimeNumber} = ${j} + ${sumOfPrimeNumber - j}`)
            found = true;
            // 다음 케이스로
            break;
        }
    }
    // 주어진 조건 성립하는 Case를 발견하지 못한 경우
    if (!found) answer.push("Goldbach's conjecture is wrong.")
}
console.log(answer.join('\n'))

 

---

 

마치며

'소수'와 '범위'라는 키워드를 통해 에라토스테네스의 체를 떠올릴 수 있다면 쉽게 풀이할 수 있는 문제였습니다.