[백준 | Javascript] 1929

기본 수학 2. 4단계
1929번. 소수 구하기

문제

1929번 문제 링크

solution1 (에라토스테네스의 체)

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split(" ").map((x) => Number(x));

const startNum = input[0];
const endNum = input[1];

// 에라토스테네스의 체
// 1. 2부터 N까지의 자연수를 나열
// 2. 처리되지 않은 수 중 가장 작은 수 i를 찾음
// 3. i의 배수를 모두 제거(i는 제거하지 않음)
// 4. 더 이상 반복할 수 없을 때까지 2,3번을 반복

// 0부터 endNum까지의 원소를 true로 만들어줌
// true는 소수, false는 소수가 아님을 의미하게 될 것
let isPrime = Array(endNum + 1).fill(true);

// 0과 1은 소수가 아니다.(심지어 0은 입력으로 들어오지도 않는다)
isPrime[0] = false;
isPrime[1] = false;

// 소수 판별 시작
for(let i = 2; i*i <= endNum; i++){
  if(isPrime[i]){
    // 소수의 배수는 소수가 아니므로, 그 것들을 찾아내기 위해 곱 연산 진행
    let multiple = 2;
    
    // 연산은 endNum보다 작을 때까지 진행할 것
    while(i * multiple <= endNum){
      isPrime[i * multiple] = false;
      multiple++;
    }
  }
}

let result = [];

// 소수 판별이 완료된 isPrime 배열 활용
// i는 startNum ~ endNum 사이의 값들
for(let i = startNum; i <= endNum; i++){
  // isPrime이 true라면 소수이므로
  if(isPrime[i]){
    // result 배열에 i를 push
    result.push(i);
  }
}

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

solution2 (일반적인 소수 판별)

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split(" ").map((x) => Number(x));

const startNum = input[0];
const endNum = input[1];

// 소수 판별
outer: for(let i = startNum; i <= endNum; i++){
  // 입력 데이터 범위에 1이 포함됨
  // 1은 소수가 아니다.
  // 따라서 i가 1인 상황을 무시할 수 없으므로, 예외 처리(continue로 다음 수로 넘어감)
  if(i === 1){
    continue;
  }
  
  inner: for(let j = 2; j*j <= i; j++){
    // j로 나눠지면 소수가 아니므로 outer 반복문에 대해 continue(i가 다음 수로 넘어감)
    if(i % j === 0){
      continue outer;
    }
  }
  
  // 위 모든 조건을 통과하면 소수
  // for문 내에서 console.log()를 하므로 startNum부터 endNum 사이의 소수는 전부 출력 가능
  console.log(i);
}

해설

이전까지의 문제는 소수를 판별하는데 있어서 3가지의 방법을 사용했다.(굳이 또 언급은 하지 않겠다)
그런데 방법이 하나 더 있었다. 바로 "에라토스테네스의 체"라는 방법이다.(소요 시간 220ms)
방법은 여기에 있다.
수의 범위가 클 경우에 사용하는 소수 판별법이라고 한다.
풀이 참고 사이트
물론 평소에 사용하던 방법으로도 해결할 수 있다.(소요 시간 4180ms)
소요시간 차이가 압도적이다...
시간 복잡도가 문제가 될 때 획기적인 솔루션이 될 수 있다!