백준 9020번: 소수 구하기(골드바흐의 추측 - 에라토스테네스의 체) Node.js(JavaScript)

https://www.acmicpc.net/problem/9020

Code

최종 제출 코드

😢 역시 에라토스테네스의 체를 이용하면 되고, 골드바흐의 파티션을 어떻게 구할지 생각을 해줘야 한다.

😊 31번째 줄 코드는 이전 문제에서 사용한 것과 같고, 33-37번째 줄 코드에서 2부터 n까지 소수를 저장해준다.

중첩 for loop을 열고, 입력 받은 n을 0으로 만들 수 있는 소수의 짝을 checkPrimePair 배열에 2차원 형식으로 저장해준다.
(checkPrimePair가 저장된 모습은 [ [2, 3], [3, 5] ] 같은 형식이라고 생각해주면 된다)

그리고 또 다시 for loop을 열고 checkPrimePair중 가장 작은 차이가 나는 소수 짝의 index를 구해준다.

마지막으로, 해당 index의 짝을 join(' ')형식으로 출력해주면 된다.

지금까지 풀었던 알고리즘 중에 가장 길지 않나 싶다. 다시 풀어보며 조금 더 개선할 수 있는 곳을 찾아봐야겠다.

Full Code (https://github.com/DasolPark/Dasol_JS_Algorithm/tree/master/Baekjoon)

// Goldbach's conjecture

// 1st Solution

// For submit

// const fs = require('fs');

// const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n').map(num => parseInt(num));

// For local test

const input = [3, 8, 10, 16];

const T = input.shift();

for (let i = 0; i < T; i++) {

const n = input.shift();

const isPrimeNumArr = new Array(n + 1);

const primeNumArr = [];

const checkPrimePair = [];

isPrimeNumArr.fill(true);

isPrimeNumArr[0] = isPrimeNumArr[1] = false;

for (let j = 2; j <= n; j++) {

if (Math.pow(j, 2) > 1000000) {

break;

} else {

for (let square = Math.pow(j, 2); square <= n; square += j) {

isPrimeNumArr[square] = false;

}

}

}

for (let i = 2; i <= n; i++) {

if (isPrimeNumArr[i]) {

primeNumArr.push(i);

}

}

for (let i = 0; i < primeNumArr.length; i++) {

for (let j = i; j < primeNumArr.length; j++) {

if (n - primeNumArr[i] - primeNumArr[j] === 0) {

checkPrimePair.push([primeNumArr[i]]);

checkPrimePair[checkPrimePair.length - 1].push(primeNumArr[j]);

}

}

}

let min = checkPrimePair[0][1] - checkPrimePair[0][0];

let indexOfMin = 0;

for (let i = 0; i < checkPrimePair.length; i++) {

if (checkPrimePair[i][1] - checkPrimePair[i][0] < min) {

min = checkPrimePair[i][1] - checkPrimePair[i][0];

indexOfMin = i;

}

}

console.log(checkPrimePair[indexOfMin].join(' '));

}