에라토스테네스의 체 ) 범위 내 소수 구하기

작성일 In Views: Disqus:

▪︎ 에라토스테네스의 체

에라토스테네스의 체는 빠르게 범위 내 소수들을 찾는 방법입니다. 하나의 수에 대해 소수인지 아닌지를 판별하는 것은 O(N)으로 해결이 가능하지만 범위 내에서 소수들을 찾기 위해서는 추가로 범위 내에 존재하는 K개의 수가 곱해진 O(N*K)의 시간복잡도를 가질 것입니다. 그러나 에라토스테네스의 체를 이용하면 O(N * log logN)의 시간복잡도로 이를 해결할 수 있습니다.

▫︎ 에라토스테네스의 체 원리

gif

step 1) 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.

step 2) 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)

step 3) 자기 자신을 제외한 2의 배수를 모두 지운다.

step 4) 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)

step 5) 자기 자신을 제외한 3의 배수를 모두 지운다.

step 6) 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)

step 7) 자기 자신을 제외한 5의 배수를 모두 지운다.

step 8) 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)

step 9) 자기 자신을 제외한 7의 배수를 모두 지운다.

step 10) 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. (보라색)

범위 최대값의 제곱근보다 작거나 같은 자연수의 배수들만 지우면 된다. 위 예시의 경우 10까지만 배수들을 지워주는 동작을 시행한다.

▫︎ 에라토스테네스의 체 구현

  1. 2부터 소수를 구하고자하는 구간의 모든 수를 배열의 인덱스를 key로 삼아 0과 1을 제외하고 모두 true로 초기화합니다.
  2. 생성한 배열을 순회하면서 value가 false인 경우 스킵하고, true인 경우 배열 내 해당 index의 배수에 위치하는 모든 값들을 false로 재할당합니다.
  3. 초기 생성한 배열에서 true를 값으로 가진 인덱스들이 소수입니다.

▪︎ Example of Apply

▫︎ 100보다 작은 소수 찾기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 소수 체크 테이블
const check = Array(Math.floor(101)).fill(true).fill(false, 0, 2);

// 100의 제곱근인 10보다 작은 자연수의 배수들만 지우기
for (let i = 2; i <= 10; i++) {
  if (!check[i]) continue;

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

// 소수 배열
const prime = [];

// 체크 테이블의 값이 true인 index가 소수
check.forEach((el, idx) => {
  if (el) prime.push(idx);
});

console.log(prime);