[백준 / BOJ] 17103번 골드바흐 파티션 (Javascript / Node js)
2023. 10. 21. 23:33ㆍ코딩 테스트 (BOJ)
https://www.acmicpc.net/problem/17103
문제 해석
골드바흐 파티션이란 4 -> 2 + 2 , 8 -> 3 + 5 와 같이 소수 두개의 합으로 나타내는 표현이라고 한다.
10의 골드바흐 파티션은 (3 + 7), (5 + 5)이 있다.
(3 + 7)과 (7 + 3)은 같은 파티션으로 간주한다고 하니, 10의 골드바흐 파티션은 2개가 나오는 것을 확인할 수 있다.
그러니 입력 받은 짝수 N을 소수로 뺀 값이 소수가 나오는 경우의 수를 세주면 되겠다.
소수들의 집합은 역시 에라또스테네스의 체를 이용해 만들어주고,
(3 + 7) 과 (7 + 3)을 같은 파티션으로 간주하니, 경우의 수를 세줄 for문의 범위는 N/2까지로 잡아줘도 된다.
에라토스테네스의 체 관련 포스팅
[백준 / BOJ] 1929번 소수 구하기 (Javascript / Node js) (tistory.com)
전체 코드
const fs = require("fs");
const input = fs
.readFileSync("../input.txt")
.toString()
.trim()
.split("\n")
.map((item) => Number(item));
input.shift();
const Eratos = (N) => {
let arr = Array(N + 1).fill(true);
let cnt = 0;
arr[0] = false;
arr[1] = false;
for (let i = 2; i <= Math.sqrt(N); i++) {
for (let j = i * i; j <= N; j += i) {
arr[j] = false;
}
}
for (let i = 0; i < arr.length; i++) {
if (arr[i]) {
if (arr[N - i]) {
cnt++;
}
}
}
if (arr[N / 2]) {
return (cnt = (cnt + 1) / 2);
} else {
return (cnt = cnt / 2);
}
};
let answer = [];
for (let i = 0; i < input.length; i++) {
answer.push(Eratos(input[i]));
}
console.log(answer.join("\n"));
'코딩 테스트 (BOJ)' 카테고리의 다른 글
[ICPC] Problem C - 행복 점수 (Java) (0) | 2023.10.22 |
---|---|
[백준/BOJ/ICPC] 16360번 Go Latin (Node js / Javascript) (0) | 2023.10.22 |
[백준 / BOJ] 4948번 베르트랑 공준 (Javascript / Node js) (0) | 2023.10.21 |
[백준 / BOJ] 1929번 소수 구하기 (Javascript / Node js) (0) | 2023.10.14 |
[백준 / BOJ] 4134번 다음 소수 (Javascript / Node js) (0) | 2023.10.13 |