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

1. 첫 제출

const [a,b] = [5,16];
let arr = [];
for (let i = a; i <= b; i++) {
  for (let j = 2; j < i; j++) {
    if (i % j === 0) {
      break;
    }
    if (j === i - 1) {
      arr.push(i);
    }
  }
}
console.log(arr.join('\n'));

시간초과로 다른 방법으로 접근이 필요했다.

 

2. 에라토스테네스의 체

소수를 찾아내는 알고리즘으로 에라토스테네스의 체를 사용하면 된다는 것을 알게되었다.

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

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

 

const input = require('fs').readFileSync('dev/stdin').toString().split(' ');
const start = +input.shift();
const end = +input.shift();
const isPrimeNumber = Array(end+1).fill(true);
isPrimeNumber[0] = isPrimeNumber[1] = false;
const result = [];

for(let i=2; i<end; i++ ){
  if(isPrimeNumber[i]){
    let m = 2;
    while(i * m <= end){
      isPrimeNumber[i*m] = false;
      m++
    }
  }
}

for(let i=start; i<=isPrimeNumber.length; i++){
  if(isPrimeNumber[i]){
    result.push(i);
  }
}
console.log(result.join('\n'))

end까지의 길이에 해당하는 배열을 만들어두고 잠정적으로 소수라고 설정하기 위해 fill(true)를 했다. 여기서 소수가 아닌 숫자들을 false로 바꿀 것이다.

0과 1은 소수가 아니므로 false로 바꾼다.

 

for(let i=2; i<end; i++ ){
  if(isPrimeNumber[i]){
    let m = 2;
    while(i * m <= end){
      isPrimeNumber[i*m] = false;
      m++
    }
  }
}

2는 소수지만 2의 배수들은 소수가 아니기에 end 보다 작은 2의 배수들은 모두 소수가 아니라고 설정을 해주기 위해 반복문을 돌렸다.

마찬가지로 3도 소수지만 3의 배수들은 소수가 아니기에 3의 배수들을 모두 소수가 아니라고 설정해주기 위해 반복문을 돌렸다.

이렇게 계속 반복하면 된다.

 

for(let i=start; i<=isPrimeNumber.length; i++){
  if(isPrimeNumber[i]){
    result.push(i);
  }
}
console.log(result.join('\n'))

 

 

마지막에 출력하면 된다.