[백준] 1929 - 소수 구하기

Jang·2022년 9월 15일

JavaScript 백준

백준

목록 보기

2/6

문제 - 소수 구하기

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

오류 - 시간 초과

문제 자체는 이전 문제와 비슷하고 어렵지 않았는데 시간초과 오류가 계속 났다.

처음 풀이

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split(" ");

const M = parseInt(input[0]);
const N = parseInt(input[1]);

let i = M;
let so = 0;
while (i <= N) {                 // i는 M이상 N이하 탐색
  for (j = 2; j < i; j++) {      // j는 2이상 i미만 탐색
    if (i % j == 0) {            // i가 j로 나눠지면 so에 0 대입 (소수가 아님)
      so = 0;					
      break;		// 해당 i에서 j반복은 종료
    }
    so = i;		// j 탐색이 끝나도 나눠지지 않으면 so에 i대입 (소수)
  }
  if (so > 0) {   // so가 0보다 크면 출력 
    console.log(so);
  }
  i++;
}

이후에도 조금씩 바꿔가면서 제출했지만 전부 시간초과.

정답 풀이

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split(" ");

const M = parseInt(input[0]);
const N = parseInt(input[1]);

if (M <= 2) {
  console.log(2);
}

let obj = { 1: true };

for (i = M; i <= N; i++) {
  for (j = 2; j <= Math.ceil(Math.sqrt(i)); j++) {
    if (i % j == 0) {
      obj[i] = true;
      break;
    }
  }

  if (!obj[i]) {
    console.log(i);
  }
}

차이점
- j의 범위를 원래는 i 미만으로 했는데 어차피 나눠지는 수는 제곱근보다 작기 때문에 Math.sqrt()를 이용해 범위를 줄였다.
  - 만약 i가 64일 때 j의 범위가 2~64 였는데 2~8 정도로 대폭 축소
  - 처음 풀이에서 범위만 이렇게 바꿔도 정답처리가 되었다.
- 에라토스테네스의 체 이용
  - M~N 에서 소수가 아닌 수들을 JSON에서 true값을 넣어줌.
  - 모든 반복이 끝나고 JSON에 undefined가 되어있는 값이 소수