백준 JS | 1929번 소수 구하기

출처: 백준 온라인저지

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

1929번: 소수 구하기

답안 ( 오답 - 시간 초과)

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

const m = +input[0];
const n = +input[1];
let answer = '';

for (let i = m; i <= n; i++) {
  for (let j = 2; j <= i; j++) {
    if (i < 2) {
      break;
    }
    if (i % j === 0 && i === j) {
      answer += j + '\n';
    } else if (i % j === 0 && i !== j) {
      break;
    }
  }
}

console.log(answer);

1. 반복문을 사용하여 m과 n 사이의 숫자들을 구한다. 

2. 구한 숫자들을 또 다시 2부터 반복문을 돌리면서 소수를 찾아서 answer 변수에 추가한다.

=> 이 로직을 따를 경우, 반드시 2번의 반복문을 중첩해야하며 2번 모두 처음부터 끝까지 모든 경우의 수에 대해 반복문이 끝나야하므로 

2초인 시간 제한을 맞출 수 없다. 

=> 앞선 베트르랑 공준과 마찬가지로 에라토스테네스의 체를 참고하여 Math.sqrt 함수를 사용하여 소수를 찾음으로써 로직을 간단하게 해야한다.

두번째 답안(오답)

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

const m = +input[0];
const n = +input[1];
let answer = '';

for (let i = m; i <= n; i++) {
  for (let j = 2; j <= Math.ceil(Math.sqrt(i)); j++) {
    if (i <= 1) {
      break;
    }
    if (i % j === 0) {
      break;
    }
    if (i % j !== 0 && j === Math.ceil(Math.sqrt(i))) {
      answer += i + '\n';
    }
  }
}

console.log(answer);

1. 반복문을 사용하여 m과 n 사이의 숫자들을 구한다. 

2. 구한 숫자들을(변수 i) 반복문을 사용하여 소수인지 체크를 하는데, 이때 사용될 변수 j는 에라토스테네스의 체를 활용하여 Math.sqrt(i) 보다 작은 수들이다. 단,  이때 숫자가 3일 경우 Math.sqrt(i) 의 값은 1.7xxx 로 2로 시작하는 j 값보다 작기 때문에 Math.ceil 을 사용한다.

3. 숫자가 1보다 작을 경우 즉, 0과 1은 소수가 아니므로 반복문을 나가도록 하고,

4. i % j 가 0인 경우도 소수가 아니므로 반복문을 나가도록 하고.

5. i % j 가 0이 아니고, j가 Math.ceil(Math.sqrt(i))) 경우 소수이므로 answer에 추가하도록 한다. 

 

=> 아마도 Math.ceil(Math.sqrt(i)) 로 반올림 했을 때,  i % j !== 0 && j === Math.ceil(Math.sqrt(i)) 조건에 어긋나는 반례가 존재하는 것 같다.

 

세 번째 답안 ( 정답  ✅ )

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

const n = +input[0];
const m = +input[1];
let isPrimeNum = Array(m + 1).fill(true);
isPrimeNum[0] = isPrimeNum[1] = false;
answer = '';

function getPrimeNum() {
  for (let i = 2; i <= Math.ceil(Math.sqrt(m)); i++) {
    if (isPrimeNum[i]) {
      let multiple = 2;
      while (i * multiple <= m) {
        isPrimeNum[i * multiple] = false;
        multiple++;
      }
    }
  }

  for (let i = n; i <= m; i++) {
    if (isPrimeNum[i]) {
      answer += i + '\n';
    }
  }

  console.log(answer);
}

getPrimeNum();

다른 사람 답안

https://velog.io/@gkswn45/JavaScript-%EB%B0%B1%EC%A4%80-1929%EB%B2%88-%EC%86%8C%EC%88%98%EA%B5%AC%ED%95%98%EA%B8%B0

JavaScript 백준 1929번 소수구하기

https://gurtn.tistory.com/150

[JS] 백준 1929번 소수 구하기