PS에서 소수를 다루는 문제는 자주 등장한다.
처음에는 에라토스테네스의 체만 익혀도 대부분의 문제를 해결할 수 있다. 실제로도 소수 판정이나 소수 목록 생성 정도라면 그것만으로 충분한 경우가 많다.
그런데 조금 더 다양한 수론 문제를 접하다 보면 단순히 “소수를 구하는 것”만으로는 부족한 순간이 생긴다. 예를 들어 어떤 수의 최소 소인수를 빠르게 알고 싶을 때, 여러 수를 반복해서 소인수분해해야 할 때, 혹은 오일러 피 함수나 뫼비우스 함수처럼 각 정수에 대한 값을 한꺼번에 전처리하고 싶을 때가 그렇다.
이럴 때 등장하는 것이 Linear Sieve이다. 이름 그대로 선형 시간에 동작하는 체이며, Euler Sieve라고 부르기도 한다.
겉으로 보기에는 에라토스테네스의 체와 크게 다르지 않아 보인다. 그러나 합성수를 처리하는 방식에는 분명한 차이가 있다. 이 글에서는 그 차이가 무엇인지, 왜 선형 시간이라고 할 수 있는지, 그리고 최소 소인수 배열을 어떻게 자연스럽게 얻을 수 있는지를 차례대로 설명하고자 한다.
Linear Sieve를 이해하려면 먼저 에라토스테네스의 체를 떠올리는 편이 좋다.
에라토스테네스의 체는 다음과 같은 방식으로 동작한다.
2부터 시작한다.- 아직 지워지지 않은 수를 소수라고 본다.
- 그 수의 배수들을 모두 지운다.
이 방식은 매우 직관적이고 구현도 간단하다. 다만 어떤 합성수는 여러 번 처리될 수 있다. 예를 들어 30은 2의 배수이기도 하고, 3의 배수이기도 하며, 5의 배수이기도 하다. 구현상으로는 이미 지워진 수를 다시 지우더라도 큰 문제가 되지 않지만, 계산의 관점에서 보면 같은 합성수가 여러 소수에 의해 반복해서 다뤄지고 있는 셈이다.
Linear Sieve는 바로 이 지점에서 출발한다.
Linear Sieve의 핵심은 다음 한 문장으로 요약할 수 있다.
각 합성수를 그 수의 최소 소인수에 의해 정확히 한 번만 처리한다.
이 말이 처음에는 다소 추상적으로 들릴 수 있다. 예를 들어 12를 생각해 보자. 12의 최소 소인수는 2이다. 그렇다면 12는 2 × 6의 형태로 처음 만들어지도록 하고, 그 이후 다른 방식으로 중복해서 처리하지 않겠다는 것이다.
즉, Linear Sieve는 합성수를 “여러 번 지우는” 방식이 아니라, 최소 소인수를 기준으로 한 번씩 생성하는 방식에 가깝다. 이 관점이 이 알고리즘 전체를 이해하는 데 가장 중요하다.
보통 Linear Sieve에서는 두 가지를 저장한다.
하나는 지금까지 찾은 소수들을 담는 배열 primes이고, 다른 하나는 각 수의 최소 소인수를 저장하는 배열 lp이다. 여기서 lp는 lowest prime factor를 뜻한다.
예를 들면 다음과 같은 식이다.
lp[2] = 2
lp[3] = 3
lp[4] = 2
lp[6] = 2
lp[15] = 3
소수의 경우 최소 소인수는 자기 자신이며, 합성수의 경우에는 가장 작은 소수가 기록된다.
이제 2부터 N까지의 정수를 차례대로 살펴본다고 하자.
어떤 수 i를 보고 있는데 lp[i]가 아직 0이라면, 이는 지금까지 어떤 방식으로도 i가 생성된 적이 없다는 뜻이다. 따라서 i는 소수이다. 이 경우에는
lp[i] = i로 두고primes배열에i를 추가한다.
그 다음에는 지금까지 구한 소수들 p를 차례로 보면서 i * p를 만든다. 그리고 그 수의 최소 소인수를 p로 기록한다.
이를 파이썬 코드로 표현하면 아래와 같다
def linear_sieve(n):
lp = [0] * (n + 1)
primes = []
for i in range(2, n + 1):
if lp[i] == 0:
lp[i] = i
primes.append(i)
for p in primes:
if i * p > n:
break
lp[i * p] = p
if p == lp[i]:
break
return primes, lp
p == lp[i] 에서 중단되는 이유를 살펴보자.
현재 i에 대해 소수 p를 곱하여 i * p를 만들고 있다고 하자. 이때 p가 lp[i]보다 큰 소수라면, i * p는 이후 다른 수에 더 작은 소수를 곱하는 방식으로 다시 등장할 수 있다. 그러면 같은 합성수를 여러 번 처리하게 된다.
반대로 p <= lp[i]인 범위에서만 곱한다면, i * p의 최소 소인수는 정확히 p가 된다. 즉, 그 수를 최소 소인수 기준으로 올바르게 한 번 생성한 것이 된다.
따라서 p == lp[i]에 도달하면 그 이후의 더 큰 소수들에 대해서는 볼 필요가 없다. 그 지점에서 중단해야만 각 합성수가 정확히 한 번만 처리되는 구조가 유지된다.
마지막으로 Linear Sieve는 처음 보면 에라토스테네스의 체와 비슷한 변형처럼 보이지만, 실제로는 합성수를 다루는 관점 자체가 다르다.
이 알고리즘의 핵심은
각 합성수를 최소 소인수 기준으로 정확히 한 번만 처리한다는 데 있다.
이 성질 덕분에 선형 시간에 소수를 구할 수 있고, 동시에 최소 소인수 배열까지 얻을 수 있다. 그리고 그 배열은 빠른 소인수분해는 물론이고, 다양한 수론 함수의 전처리로 자연스럽게 이어진다.
Comments ()