[백준] 1929: 소수 구하기 (javascript)

Link

1929번: 소수 구하기

문제

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

입력 > 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000)
M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
출력 > 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

| 예제 입력

3 16

| 예제 출력

3
5
7
11
13

 

제출

const input = (
  process.platform == "linux"
    ? require("fs").readFileSync("/dev/stdin").toString()
    : `3 16`
)
  .split(" ")
  .map(Number);

const [M, N] = input;

const isPrimeNumber = new Array(N + 1).fill(true);
isPrimeNumber[0] = isPrimeNumber[1] = false;

for (let i = 2; i <= Math.ceil(Math.sqrt(N)); i++) {
  if (!isPrimeNumber[i]) {
    continue;
  }

  for (let j = i * 2; j <= N; j += i) {
    isPrimeNumber[j] = false;
  }
}

const results = [];

for (let i = M; i <= N; i++) {
  if (isPrimeNumber[i]) {
    results.push(i);
  }
}

console.log(results.join("\n"));

 

풀이과정

첫 번째 제출 - 시간 초과

const input = (
  process.platform == "linux"
    ? require("fs").readFileSync("/dev/stdin").toString()
    : `3 16`
)
  .split(" ")
  .map(Number);

const [M, N] = input;
let primeNumber = [];

for (let i = M; i <= N; i++) {
  let arr = [];

  if (i === 1) {
    continue;
  }

  for (let j = 2; j <= i; j++) {
    i % j === 0 && arr.push(j);
  }

  arr.length === 1 && primeNumber.push(i);
}

for (let i of primeNumber) {
  console.log(i);
}

 

모든 수에 대해서 나누고, 나누어 떨어질 때, 몫이 하나라면 소수라는 점을 이용하면 시간 초과가 된다.

따라서, 이전 문제에서 풀었을 때처럼 어떤 수의 배수일 경우 소수가 아니라는 것을 활용해야 한다.

이러한 개념을 에라토스테네스의 체라고 하며, 숫자의 범위가 넓을 때 소수를 찾을 경우에 사용된다.

 

기존에 모든 수의 약수를 체크하면서 소수를 찾을 경우 시간 복잡도가 O(N)인 반면, 

에라토스테네스의 체를 사용하면 해당 수의 제곱근까지 비교하기 때문에 시간 복잡도가 O(N^1/2)로 줄어들게 된다.

 

두 번째 제출 - 정답, 에라토스테네스의 체 사용하기

const input = (
  process.platform == "linux"
    ? require("fs").readFileSync("/dev/stdin").toString()
    : `3 16`
)
  .split(" ")
  .map(Number);

const [M, N] = input;

const isPrimeNumber = new Array(N + 1).fill(true);
isPrimeNumber[0] = isPrimeNumber[1] = false;

for (let i = 2; i <= Math.ceil(Math.sqrt(N)); i++) {
  if (!isPrimeNumber[i]) {
    continue;
  }

  for (let j = i * 2; j <= N; j += i) {
    isPrimeNumber[j] = false;
  }
}

const results = [];

for (let i = M; i <= N; i++) {
  if (isPrimeNumber[i]) {
    results.push(i);
  }
}

console.log(results.join("\n"));

에라토스테네스의 체를 활용해서 2부터 N까지 소수는 true 값을 갖는 isPrimeNumber를 만든다.

 

배열의 값이 true 라면 소수라는 의미이기 때문에 isPrimeNumber의 M부터 N까지의 인덱스 중 true인 경우

results 배열에 해당 값을 push 하여 출력한다.

 

 

개념

에라토스테네스의 체

• 2부터 소수를 구하고자 하는 수 까지 나열한다.
• 2는 소수이므로 자기 자신을 제외한 2의 배수들을 모두 지운다.
• 3은 소수이므로 자기 자신을 제외한 3의 배수들을 모두 지운다.
• 이를 반복해서 남은 숫자들은 소수가 된다.

위 그림에서 11² > 120 이므로, 11보다 작은 배수까지 비교하면 된다.

 

LINK

 

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

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

 

 

---

Comment

난이도가 올라가자마자,, 버벅였던 나,, ㅎㅎㅎㅎ

첫 수정 이후, isPrimeNumber 배열을 만들 때 M - N + 1개 배열을 만들면 되겠지 ~ 라고 생각해서 틀린 답이 나왔다.

0부터 N까지의 isPrimeNumber 배열을 만들어놔야 하므로 N + 1개 배열을 생성해야했다😅