골드바흐의 추측(Goldbach's conjecture)은 오래전부터 알려진 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 개의 소수(Prime number)의 합으로 표시할 수 있다는 것이다. 이때 하나의 소수를 두 번 사용하는 것은 허용한다. - 위키백과
위 설명에서 2보다 큰 모든 짝수를 두 소스의 합으로 나타낸 것을 골드바흐 파티션이라고 합니다.
예)
100 == 47 + 53
56 == 19 + 37
2보다 큰 짝수 n이 주어졌을 때, 골드바흐 파티션을 출력하는 코드를 작성하세요.
* 해당 문제의 출력 형식은 자유롭습니다. 가능하시다면 골드바흐 파티션 모두를 출력하거나, 그 차가 작은 것을 출력하거나 그 차가 큰 것 모두 출력해보세요.
/**
* n까지의 인덱스를 가진 배열에서 n이 소수라면 true, 아니라면 false를 해주고
*
* 그 배열을 리턴해주는 함수
* @param {Number} n 2보다 큰 짝수
* @param {Boolean[]} arr true로 초기화된 n의 길이를 가진 배열
* @returns {Boolean[]} n의 길이를 가진 각 인덱스가 소수인지 아닌지 판별 완료된 배열
*/
function isPrime(n, arr) {
for (let i = 2; i * i <= n; i++) {
if (arr[i] === true) {
for (let j = i * 2; j <= n; j += i) {
arr[j] = false;
}
}
}
return arr;
}
/**
* 모든 골드바흐 파티션을 출력해주는 함수
* @param {Number} n 2보다 큰 짝수
* @param {Boolean[]} prime_arr n의 길이를 가진 각 인덱스가 소수인지 아닌지 판별 완료된 배열
*/
function printAllGoldbach(n, prime_arr) {
for (let i = 2; i <= n; i++) {
for (let j = 2; j <= n; j++) {
if (prime_arr[i] && prime_arr[j] && i + j === n) {
console.log(`${i + j} == ${i} + ${j}`);
}
}
}
}
/**
* 가장 차이가 작은 골드바흐 파티션을 출력해주는 함수
* @param {Number} n 2보다 큰 짝수
* @param {Boolean[]} prime_arr n의 길이를 가진 각 인덱스가 소수인지 아닌지 판별 완료된 배열
*/
function printMinDistanceGoldbach(n, prime_arr) {
for (let i = 2; i <= n; i++) {
for (let j = 2; j <= n; j++) {
if (prime_arr[i] && prime_arr[j] && i + j === n) {
if (i >= j) {
console.log(`${i + j} == ${j} + ${i}`);
console.log(`${i + j} == ${i} + ${j}`);
return;
}
}
}
}
}
/**
* 가장 차이가 큰 골드바흐 파티션을 출력해주는 함수
* @param {Number} n 2보다 큰 짝수
* @param {Boolean[]} prime_arr n의 길이를 가진 각 인덱스가 소수인지 아닌지 판별 완료된 배열
*/
function printMaxDistanceGoldbach(n, prime_arr) {
for (let i = 2; i <= n; i++) {
for (let j = 2; j <= n; j++) {
if (prime_arr[i] && prime_arr[j] && i + j === n) {
console.log(`${i + j} == ${i} + ${j}`);
console.log(`${i + j} == ${j} + ${i}`);
return;
}
}
}
}
function solution(n) {
let prime_arr = Array.from({ length: n }, () => true);
prime_arr[0] = prime_arr[1] = false;
prime_arr = isPrime(n, prime_arr);
printAllGoldbach(n, prime_arr);
console.log("---------------------------------------");
printMinDistanceGoldbach(n, prime_arr);
console.log("---------------------------------------");
printMaxDistanceGoldbach(n, prime_arr);
}
const n = 100;
solution(n);
소수를 구하는 방식은 '에라토스테네스의 체' 알고리즘을 사용하였다. (이전에 따로 정리한 아래 포스팅 참조)
2022.01.16 - [ALGORITHM/etc] - 에라토스테네스의 체
따라서 소수 배열을 구했다면, 두 소수의 합이 주어진 수인지만 판단하여 출력해주면 된다.
단, 가장 차가 작은 골드바흐 파티션을 구할 때의 방법을 특이하게 했는데,
만약 문제에서 주어진대로 100의 모든 골드바흐 파티션을 구하게 된다면
...
100 == 47 + 53
100 == 53 + 47
...
위와 같이 될것이다.
따라서 골드바흐 파티션은 중심으로 대칭을 이루는 구조이다.
가능한 모든 골드바흐 파티션을 나열했을 때, 중심에 가까울수록 그 차가 적다는것을 알 수 있다.
따라서 첫번째 수가 두번째 수보다 커지는 순간이 대칭수가 되는것이므로 그때의 조건을 달아주어 구했다.
차가 제일 큰 경우는 맨 처음과 맨 마지막이므로 맨 처음의 골드바흐 파티션만 구해서 위치를 바꿔주어
똑같이 대칭수를 출력해주면 된다.
'PS > 제코베 JS 100제' 카테고리의 다른 글
제코베 JS 100제 / 71 / 깊이 우선 탐색 (0) | 2022.09.13 |
---|---|
제코베 JS 100제 / 70 / 행렬 곱하기 (0) | 2022.09.09 |
제코베 JS 100제 / 68 / 버스 시간표 (0) | 2022.09.08 |
제코베 JS 100제 / 67 / 민규의 악수 (0) | 2022.09.08 |