1929 - 소수 구하기 - node.js

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

1929번: 소수 구하기

---

2022.08.29 - [백준 문제 풀이/문제 풀이] - 2581 - 소수 - node.js

소수 구하기 문제이기 때문에 이전에 제출했던 방법을 수정해서 해결할 수 있지 않을까 생각했고 실제로 그렇게 제출했더니...

결과 시간초과로 실패하게 되었다. 이전의 문제보다 더 빠르게 답을 구해내야 하는 문제, 이전의 문제에서는 만약 M~N까지의 범위가 있다고 치면 모든 수에 대해서 2로 나눴다가 아니면 3으로 나누고 아니면 4로 나누고... 이렇게 반복하게 되었다. 그렇게 되면 자연스럽게 계산할 필요 없는 것까지도 중복해서 계산이 된다.

예를 들어서 2로 나눠 떨어지는 수라면 2의 배수들 4, 6, 8로 계산할 필요가 없다. 2로 계산이 되기 때문에 자연히 소수가 아니게 되기 때문이다. 마찬가지로 3의 경우에도 6, 9, 12 등도 소수가 아니게 되기 때문에 계산할 필요가 없다.

구글 검색 결과 나오는 것이 에레토스테네스의 체 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

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

1. 2부터 시작해서 구하고자 하는 구간의 모든 수를 나열하고

2. 2부터 시작, 소수이므로 array에 추가하고 그 배수들을 모두 지운다.

3. 남은 수를 대상으로 다시 시작, 3은 소수이므로 array에 추가하고 그 배수들을 모두 지운다.

4. 계속 반복

=> 가장 처음 수부터 시작해서 소수라면 그 배수들을 다 지우고, 지워진 수들 중에서 다시 첫 번째는 배수로 하고 그 배수를 지우는 방식이다.

친절하게도 위키의 아래에 C++ 등으로 구현하는 방법까지 자세히 설명되어 있다.

 

const input = require("fs").readFileSync("/dev/stdin").toString().trim().split(" ");
const [L, H] = input.map(Number);
let arr = [];
let result = "";

for (let i = 0; i <= H; i++) {
  arr.push(true);
}

arr[0] = false;
arr[1] = false;

for (let j = 2; j <= H; j++) {
  if (arr[j]) {
    for (let k = 2; k <= H / j; k++) {
      arr[j * k] = false;
    }
  }
}
for (let l = L; l <= H; l++) {
  if (arr[l]) result += l + "\n";
}
console.log(result.trim());

파일을 받아온 다음 L에는 최소 범위, H에는 최대 범위의 값을 지정해줬다. 빈 배열 arr에는 우선 지정된 범위의 수로 에라토스테네스의 체로 거를 대상이 되는 값들을 넣어줄 예정이고 result에는 답으로 제출할 소수들이 들어갈 자리를 만들어준다.

우선 에라토스테네스의 체의 첫 단계, 0부터 최대 범위의 숫자까지를 채워준다. true로 채워줬는데 true는 곧 소수라는 뜻이다. 우선은 전부 다 true로 채워준다.

arr[0], arr[1]은 각각 숫자 0과 1이므로 소수가 아니다. 따라서 false라고 바꿔준다.

이제 특정 수를 계산했다면 그 곱들을 전부 다 false로 바꿔주는 작업 예를 들어서 2라면 2의 배수 3이라면 3의 배수들을 전부 다 false로 바꿔주는 작업을 진행하면 된다.

for문을 중첩해서 j가 2일 때 그 안의 for문에서 k값을 돌면서 2의 배수들을 계산해나가면서 j * k 그러니까 2의 배수들을 전부 다 false로 바꿔준다. 그 다음에는 3의 배수.. 이런 식으로 진행하면서 에라토스테네스의 체의 방법을 실현할 수 있다.

이상의 과정을 전부 다 돌았다면 배수들에 대해서 걸러내는 작업이 끝났을 것이고 arr안에 남은 true들에 해당하는 값은 곧 소수일 것이다.

for문에서 L부터 H까지 돌면서 true라면 결과를 출력할 result에 넣어주는 방식으로 결과를 출력하면 된다.