99클럽 코테 스터디 1일차 TIL - 소수 구하기

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

첫 번째 시도

• 소수인지 판별하는 isPrime 함수를 만들어 isPrime이면 console.log에 출력하는 방식으로 풀이
• 1은 소수가 아니지만, for 루프를 돌지 않아서 기본적으로 true를 반환하여 실패

const isPrime = (num) => {
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) return false;
  }
  return true;
}

두 번째 시도(최종 제출 코드)

• num이 2보다 작을 때 false를 return 하도록 수정

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString();
const [m, n] = input.split(" ").map(Number);

const isPrime = (num) => {
  if (num < 2) return false; // 추가
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) return false;
  }
  return true;
}

for (let i = m; i <= n; i++) {
  if (isPrime(i)) console.log(i);
}

에라토스테네스의 체

에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 사용하면 좀 더 효율적으로 문제를 해결할 수 있음

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString();
const [m, n] = input.split(" ").map(Number);

const primeCheck = Array(n + 1)
const prime = []
primeCheck[0] = 1 // 0은 소수가 아님
primeCheck[1] = 1 // 1도 소수가 아님

for (let i = 2; i * i <= n; i++) {
  if (!primeCheck[i]) {
    for (let j = i * i; j <= n; j += i) {
      primeCheck[j] = 1 // i의 배수는 소수가 아님
    }
  }
}

for (let i = m; i <= n; i++) {
  if (!primeCheck[i]) prime.push(i)
}

console.log(prime.join('\n'))

• primeCheck[i] === 1이면 소수가 아님
• 내부 반복문에서 j = i * i부터 시작하는 이유
  - i보다 작은 수들의 배수는 이미 처리되었기 때문
  - 예: i = 3이면, 3, 6, 9, 12, ... 중 6은 이미 2에서 지워졌으므로 9부터 시작
• prime.join('\n')을 사용해 console.log 호출 최적화