백준 1929번: 소수 구하기(에라토스테네스의 체) Node.js(JavaScript)

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

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면 소수)

아래 링크를 참고하면 이론과 함께 시각적으로 어떻게 진행되는지 볼 수 있어 좋다. 좋은 참고자료!

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

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);

}

}