JS) BoJ 1929 소수 구하기/ 에라토스테네스의 체

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력 1 복사

3 16

예제 출력 1 복사

3 5 7 11 13

 

 

소수 구하는 것은 해보았으니 그대로 적용해보았다

// 입력
const fs = require('fs');
const filePath = process.platform === 'linux'? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().split(' ').map(item=>+item);

let num1 = input[0]; // 첫째 수
let num2 = input[1]; // 두번째 수

// 둘 다 3보다 작을 시
if (num1<3 && num2<3) {
  let primeNum = [1,2]
  if (num2 == 2) return console.log(2);
}

// 둘이 같은 수일 때
if (num1==num2) {
  let isPrime = true;
  for (let i = 2; i < num2; i++) {
    if (num2%i == 0) {
      isPrime = false;
      break;
    }
    isPrime = true;  
  }
  if (isPrime) {
    return console.log(num2);
  } else return ;
}

// 둘이 다른 수일 때

let isPrime = true;
while (num1<=num2) {
  for (let j = 2; j < num1; j++) {
    if (num1%j == 0) {
      isPrime = false;
      break;
    } 
  }
  if (isPrime) {
    console.log(num1); // 숫자를 줄바꿈으로 출력해야해서 바로 log로 출력해줌
  }
  isPrime = true;
  num1++;
}


/*

다른 방법 

for (let i = num1; i <= num2; i++) {
  // num1에서 +1 하면서 소수인지 확인해야 하기 때문에 반복문 사용
  for (let j = 2; j < i; j++) {
    if (i%j == 0) {
      isPrime = false;
      break;
    }
    isPrime = true;  
  }
  if (isPrime) {
    console.log(i); // 숫자를 줄바꿈으로 출력해야해서 바로 log로 출력해줌
  }
}
*/

하지만 시간 초과가 나온다

주어진 수에 그보다 작은 수를 모두 나누어 비교하다 보니 시간 초과가 생긴 것이다.

 

문제 설명에도 "에라토스테네스의 체"를 이용하라고 나온다.

 

소수인지 확인할 때는 주어진 수의 제곱근까지만 나누어보는 것!

고대 수학자들은 대단한 것 같다.

 

// 입력
const fs = require('fs');
const filePath = process.platform === 'linux'? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().split(' ').map(item=>+item);

let num1 = input[0]; // 첫째 수
let num2 = input[1]; // 두번째 수


let isPrime = true;
let sqrNum = Math.sqrt(num1)
while (num1<=num2) {
  isPrime = true;
  sqrNum = Math.sqrt(num1);
  for (let i = 1; i < sqrNum; i++) {
    if (num1%(i+1) == 0) {
      isPrime = false;
      break;
    } 
  }
  if (num1 != 1 && num1 != 2) {
    if (isPrime) console.log(num1);
  } else {
    if (num1 == 2) console.log(2);
  }
  num1++;
}

 

에라토스테네스의 체에 맞춰서 나온 코드

 

막상 풀어보니 굳이 케이스 나눌 필요 없이

반복문을 돌리고 작은 수가 1인지 2인지만 확인해서 출력 케이스만 나누어주면 된다.