[백준] 1929번 소수 구하기 (JavaScript)

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

1929번: 소수 구하기

 

(1) 내 답안

const input = require("fs")
  .readFileSync("./example.txt")
  .toString()
  .trim()
  .split("\n");

const [start, end] = input.shift().split(" ").map(Number);
const uniqueNum = Array.from({ length: end - start + 1 }, (v, i) => i + start);

uniqueNum.forEach((item, idx) => {
  for (let i = 2; i <= Math.sqrt(item); i++) {
    if (item % i == 0) {
      uniqueNum[idx] = 0;
    }
  }
});
console.log(uniqueNum.filter((a) => a !== 0 d).join("\n"));

 

(2) 모범 답안

const input = require("fs")
  .readFileSync("./example.txt")
  .toString()
  .trim()
  .split("\n");

const [start, end] = input.shift().split(" ").map(Number);
const uniqueNum = [];

for (let num = start; num <= end; num++) {
  if (num < 2) continue;
  let isPrime = true;

  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) {
      isPrime = false;
      break;
    }
  }

  if (isPrime) {
    uniqueNum.push(num);
  }
}

console.log(uniqueNum.join("\n"));

 

이 문제는 그냥 반복문을 두 개 돌리면 시간초과가 무조건 뜬다. 따라서 에라토스테네스의 체 방법을 사용해야 한다.

 

에라토스테네스는 아래의 gif로 간단 설명이 가능하다. (즉, 소수가 아닌 숫자를 지워 소수만 남기는 것이다.)

출처 - 에라토스테네스의 체 / 위키백과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

 

(1) 내 답안과 (2) 모범 답안의 차이는 시간 차이가 꽤나 난다. 되도록이면 (2) 방안으로 하는 것을 추천한다.

위-(2) 아래(1) 속도차이와 메모리차이가 많이 난다.