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

풀이 1

const input = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './ex.txt')
  .toString()
  .trim()
  .split(' ')
  .map( n =>  Number(n))

  for(let n = input[0]; n<=input[1]; n++){
    if(isPrime(n)){
      console.log(n)
    }
  }

  function isPrime(number){
    if(number === 1){
      return false
    }
    for(let a = 2; a<=Math.floor(Math.sqrt(number)); a++){
      if(number % a === 0){
        return false
      }
    }
    return true
  }

17288kb/4212ms
isPrime 함수를 이용해 풀었다. 약수는 number의 제곱근 이상에서 나오지 않는것이 포인트이다.

풀이2

const input = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './ex.txt')
  .toString()
  .trim()
  .split(' ')
  .map( n =>  Number(n))

  const [m, n] = input
  let currentNumber;
  let array = Array(n).fill(true)
  array[0] = false
  for(let i = 1; i<=Math.floor(Math.sqrt(n)); i++){
    currentNumber = i + 1
    let j = 2;
    while(currentNumber*j <= n){
      array[currentNumber*j - 1] = false
      j++
    }
  }
  for(let i = m-1; i<=n; i++){
    if(array[i]){
      console.log(i+1)
    }
  }

(28272kb/4476ms)
에라토스테네스의 체로 풀어보았다. array에 같은 수를 채우는 것은 시간복잡도면에서 큰 영향을 끼치지 않는다. 그 중에 어떤 수의 배수를 제외한다.(단, 해당 하는 수는 지우지 않기에 j = 2에서 부터 제외한다)

문제는 에라토스테네스의 체를 이용해도, 풀이 1보다 오히려 시간복잡도가 크게 나타났다. 그렇다면 에라토스테네스의 체를 왜 이용하는것일까?

다른 사람의 풀이