Code
😢 원리를 이해하고 코드를 구현하는 데, 시간이 조금 걸렸다. 여러 자료도 참고했다.
😊 에라토스테네스의 체 방법으로 소수를 구하는 문제다.
소수를 구하면, 그 소수의 배수는 소수가 될 수 없다. 그래서 그 배수들을 사전에 제거하고 남은 수를 이용해 소수를 구하는 방법이다.
먼저, (1 ≤ M ≤ N ≤ 1,000,000)이므로 MAX를 선언해준다.
그리고 소수를 판단할 isPrimeArr(Array)를 N+1만큼 선언해준다(인덱스를 N까지 사용할 것이므로)
isPrimeArr는 .fill()을 이용해 모두 true값으로 세팅해줬다. 그리고 0과 1은 소수가 아니므로 false를 세팅해줬다.
for loop을 돌리면서 해당 소수의 배수는 false로 값을 바꿔준다. 그리고 조건문을 이용해 우리가 구할 숫자를 넘어가면 break;
내부 for loop에서 for조건문의 마지막을 넣지 않았는데, 그 안에 square += i를 넣어줘도 된다. 같은 의미다(배수를 계속 더해줌)
마지막에 입력 받은 구간만큼 for loop을 이용해 출력해주면 된다(isPrimeArr이 true면 소수)
아래 링크를 참고하면 이론과 함께 시각적으로 어떻게 진행되는지 볼 수 있어 좋다. 좋은 참고자료!
에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 수학에서 에라토스테네스의 체는 소수(소쑤)를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[편집] 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초
ko.wikipedia.org
Full Code (https://github.com/DasolPark/Dasol_JS_Algorithm/tree/master/Baekjoon)
| // Find Prime Number(에라토스테네스의 체) |
| // For submit |
| // const fs = require('fs'); |
| // const input = fs.readFileSync('/dev/stdin').toString().trim().split(' ').map(num => parseInt(num)); |
| // For local test |
| const input = [3, 16]; |
| const MAX = 1000000; |
| let M = input.shift(); |
| let N = input.shift(); |
| let isPrimeArr = new Array(N + 1); |
| let square = 0; |
| isPrimeArr.fill(true); |
| isPrimeArr[0] = isPrimeArr[1] = false; |
| for (let i = 2; i < N + 1; i++) { |
| if (isPrimeArr[i]) { |
| if (parseInt(Math.pow(i, 2)) > MAX) { |
| break; |
| } else { |
| for (square = parseInt(Math.pow(i, 2)); square < N + 1; ) { |
| isPrimeArr[square] = false; |
| square += i; |
| } |
| } |
| } |
| } |
| for (let i = M; i < N + 1; i++) { |
| if (isPrimeArr[i]) { |
| console.log(i); |
| } |
| } |
'Algorithm > JavaScript(Node.js)' 카테고리의 다른 글
| 백준 9020번: 소수 구하기(골드바흐의 추측 - 에라토스테네스의 체) Node.js(JavaScript) (0) | 2020.01.24 |
|---|---|
| 백준 4948번: 소수 구하기(베르트랑 공준 - 에라토스테네스의 체) Node.js(JavaScript) (0) | 2020.01.22 |
| 백준 2581번:소수(Prime Number's Sum and Min) Node.js(JavaScript) (0) | 2020.01.21 |
| 백준 1978번: 소수 찾기(Find Prime Number) Node.js(JavaScript) (0) | 2020.01.21 |
| 백준 10872번: 팩토리얼(Factorial) Node.js(JavaScript) (0) | 2020.01.21 |
