[boj] 17103. 골드바흐 파티션

[boj] 17103. 골드바흐 파티션

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

17103번: 골드바흐 파티션

골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

---

 

1. 문제 분석

주어진 수에 대한 소수들의 합의 경우의 수를 구하는 문제입니다.
합을 구하기 위해 주어진 수의 범위 내에 있는 소수들을 모두 구해야 하기에 시간 초과를 피하기 위해 에라토스테네스의 체를 사용합니다.
에라토스테네스의 체 완성 후 합을 구하는데 중복되는 합의 시나리오는 세지 않는다고 하였으므로 테스트 케이스의 절반까지만 검사하도록 합니다.

 

소수

---

 

2. 솔루션

const fs = require('fs')
const [T, ...groupOfCases] = fs.readFileSync(process.platform ===
                                     'linux' ? '/dev/stdin' : 'input.txt')
                       .toString().trim().split('\n').map(num => +num)
const answer = []

// 에라토스테네스의 체의 크기 셋팅
const maxNumber = Math.max(...groupOfCases)

// 에라토스테네스의 체 초기화
const sieve = Array.from({length: maxNumber }, (v, k) => true)
sieve[0] = false
sieve[1] = false
for(let i = 2; i * 2 <= maxNumber; i++) {
    if(sieve[i] === false) continue;
    for(let j = i * 2; j <= maxNumber; j += i) {
        sieve[j] = false;
    }
}

for(let i = 0; i < T; i++) {
    const currentCaseNumber = groupOfCases[i]
    let count = 0;
    // 중복 값 세지 않기 위해 테스트 케이스의 절반 값까지만 검사
    for(let j = 2; j * 2 <= currentCaseNumber; j++) {
        // 현재 체의 값이 소수이고 테스트 케이스에서 현재 값을 뺀 값 또한 소수인 경우 카운터 업
        if(sieve[j] && sieve[currentCaseNumber - j]) count++;
    }
    answer.push(count)
}

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

 

---

마치며

범위 내에 있는 소수들을 구해야 하는 문제의 경우 시간초과를 피하기 위해 에라토스테네스의 체를 사용하도록 합시다.