[Baekjoon] 17103 - 골드바흐 파티션

😀문제

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

---

😁입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

---

😂출력

각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

예제 입력 1 
5
6
8
10
12
100
예제 출력 1 
1
1
2
1
6

---

🤣출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: djm03178
• 문제의 오타를 찾은 사람: jh05013

---

😃알고리즘 분류

• 수학
• 정수론
• 소수 판정
• 에라토스테네스의 체

---

😎나의풀이

기존코드, 골드바흐 파티션 수를 판별하는 과정에서 이중 반복문을 사용함(투 포인터 개념)

for(let i = 0 ; i < curPrimes.length ; i ++) {
  for(let j = curPrimes.length - 1 ; j >= i ; j --) {
    const curSum = curPrimes[i] + curPrimes[j]
    if(curSum === curNum) {
      GoldbachCount++
      break
    }
  }
}

결과는 실패, 두 소수의 합으로 특정한 수를 가르킨다는 의미를 재해석하자면
특정한 수에서 한 소수를 뺀 값이 소수라면 이는 골드바흐 파티션이 가능함을 의미하기에 한 번의 반복으로 끝낼 수 있음

// 객체는 특정 수 - 소수 의 차잇값이 소수인지 확인하기 위한 소수모음
// 배열의 경우 includes 사용으로 인한 시간초과 발생
const curPrimesDict = {}
const curPrimesArr = []
for(let i = 2 ; i <= 1_000_000 ; i++) {
    if(isPrime(i)) {
        curPrimesDict[i] = 1
        curPrimesArr.push(i)
    }
}
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split("\n").map((a, i) => {
    if(i === 0) return a
    const curNum = Number(a)
    const loopCondition = Math.floor(curNum/2)
    let GoldbachCount = 0
    for(let i = 0 ; curPrimesArr[i] <= loopCondition ; i ++) {
        const prime = curPrimesArr[i]
        // 현재 수에서 특정 소수를 뺀 값이 소수라면, 두 소수의 합으로 만들 수 있음 즉, 골드바흐 파티션
        const gap = curNum - prime
        const isCurPrime = curPrimesDict[gap]
        if(isCurPrime) GoldbachCount++
    }
    
    return GoldbachCount
})
function getPrimes(n) {
    const primes = []
    for(let i = 2 ; i <= n ; i++) {
        if(isPrime(i)) primes.push(i)
    }
    return primes
}
function isPrime(n) {
    if(n <= 1) return false
    if(n !== 2 && n%2 === 0) return false
    for(let i = 3; i <= Math.sqrt(n) ; i+=2) {
        if(n%i === 0) return false
    }
    return true
}
input.shift()

const result = input.join("\n")

console.log(result)