728x90
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(' ')); |
| } |
'Algorithm > JavaScript(Node.js)' 카테고리의 다른 글
| 백준 4153번: 직각삼각형(피타고라스의 정리) Node.js(JavaScript) (0) | 2020.01.27 |
|---|---|
| 백준 1085번: 직사각형에서 탈출 Node.js(JavaScript) (0) | 2020.01.25 |
| 백준 4948번: 소수 구하기(베르트랑 공준 - 에라토스테네스의 체) Node.js(JavaScript) (0) | 2020.01.22 |
| 백준 1929번: 소수 구하기(에라토스테네스의 체) Node.js(JavaScript) (0) | 2020.01.22 |
| 백준 2581번:소수(Prime Number's Sum and Min) Node.js(JavaScript) (0) | 2020.01.21 |
