수학·정수론O(N log log N)

에라토스테네스의 체

배수를 미리 지워, N 이하의 소수를 한 번에 걸러내요.

이럴 때 써요

어떤 범위 안의 소수를 전부 필요로 할 때
여러 수의 소수 여부를 반복해서 물어볼 때 — 미리 걸러두면 조회가 O(1)이에요
소인수분해를 아주 많이 해야 할 때 — 최소 소인수 배열을 곁들이면 분해가 빨라져요

개념

수 하나하나를 √n으로 판별하는 대신, 2부터 각 소수의 배수를 미리 지워 나가는 방법이에요. 2의 배수(4, 6, 8 …), 3의 배수(9, 15 …)를 지우다 보면, 지워지지 않고 남은 수가 곧 소수예요. N까지의 소수를 통째로 O(N log log N)에 얻어요.

"20 이하의 소수" — 배수를 지우고 남은 수
2부터 각 소수의 배수를 지워요.  · = 지워진 수
         2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
i=2 :    2  3  ·  5  ·  7  ·  9  · 11  · 13  · 15  · 17  · 19  ·
i=3 :    2  3  ·  5  ·  7  ·  ·  · 11  · 13  ·  ·  · 17  · 19  ·
i=4 :  이미 지워졌어요, 건너뛰어요
i=5 :  5 * 5 = 25 > 20 이라 멈춰요
남은 수 = 2, 3, 5, 7, 11, 13, 17, 19

상황	방법	복잡도
수 하나가 소수인지	`√n` 나눗셈	`O(√n)`
`N` 이하 소수 전부	에라토스테네스의 체	`O(N log log N)`
여러 수를 각각 판별	체로 걸러 두고 조회	만들 때 한 번 + 조회 `O(1)`

지울 때 각 수의 최소 소인수(가장 작은 약수) 를 함께 적어 두면, 소인수분해도 나눗셈 없이 O(log n)에 끝나요. 소인수분해 유형으로 이어지는 확장이에요.

패턴 코드

체로 N 이하 소수 목록 만들기isPrime 배열을 true로 채워 두고, 소수의 배수만 false로 지워요. 마지막에 true로 남은 자리가 소수예요.

javascript
Copy code
function primesUpTo(n) {
  const isPrime = new Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false;
  for (let i = 2; i * i <= n; i++) {
    if (!isPrime[i]) continue;
    for (let j = i * i; j <= n; j += i) {
      isPrime[j] = false;
    }
  }
  const primes = [];
  for (let i = 2; i <= n; i++) {
    if (isPrime[i]) primes.push(i);
  }
  return primes;
}

이 유형으로 풀어보기

이 유형에 딱 맞는 문제는 아직 준비 중이에요. 개념과 코드로 먼저 감을 잡아 두세요.

← 소수 판별 최대공약수와 최소공배수 →