오일러의 체 : 에라토스테네스의 체보다 빠른 소수 찾기, 소인수분해

에라토스테네스의 체의 경우 대부분의 합성수를 2번 이상 판정하는 문제가 있다.
당장 6만 봐도 2의 배수에서 판정하고 3의 배수에서 한번 더 판정한다. 2310(2×3×5×7×11)같은 수는 5번 판정한다. 이로 인해 O(N)보다 살짝 더 느리다. (O(NloglogN)이라고 한다)


오일러의 체(Linear Sieve)는 모든 수를 딱 한 번씩만 판정하는 알고리즘이다. 실행한 뒤에는 N 이하 수의 spf(최소 소인수 : smallest prime factor) 리스트와 소수 리스트를 얻을 수 있다. 또한 spf 리스트로 빠른 소인수분해가 가능하다.

Python 코드

N = int(input()) 
spf = [0] * (N+1) # 최소 소인수, 즉 소인수중 가장 작은 값을 저장하는 리스트. 예를 들어 spf[6] = 2, spf[9] = 3이다.
prime_set = [] # 소수를 저장하는 리스트

for i in range(2, N+1): # i = 2부터 N까지
    if not spf[i]: # spf가 0인 경우(기록되어있지 않은 경우) : 최소 소인수가 자기 자신이라는 뜻이다. 즉 소수이다.
        prime_set.append(i) # 소수 리스트에 추가
        spf[i] = i # 소수 i의 spf는 i이다.

    for p in prime_set: # 현재 prime_set에 있는 소수들에 대해
        if i * p > N: # N이 넘는 값은 판정할 필요가 없으므로 탈출하고 다음 i로 간다.
            break
        spf[i*p] = p  ##### 하단 해설 참고 #####
        if i % p == 0: ##### 하단 해설 참고 #####
            break

이 알고리즘의 목적은 합성수를 딱 한번만 판정하는 것이다.

위 코드에서는 각 수의 spf를 단 한 번만 기록한다. 그리고 소수 판정은 i에 대해 for문을 돌리면서 그 수의 spf가 이미 기록되어 있는가로 판단한다. 따라서 O(N)만에 소수 리스트를 생성할 수 있다.

spf가 단 한 번씩만 기록될 수 있는 원리는 다음과 같다.

우선 임의의 2 이상의 정수 n을 x * spf[n] = n로 표현할 수 있다. (ex. 15×2=30, 9×3=27)

n의 spf는 단 하나만 존재하므로 n에 대응하는 x 역시 단 하나만 존재한다.
따라서 x에 적절한 소수를 곱해주면 n을 표현할 수 있고, 그 '적절한 소수'가 spf[n]이 된다.

n = 30을 예로 들어본다. 다음은 spf[30] = 2를 기록하는 과정이다.

현재 30은 누군가가 내 spf를 알려주기를 기다리고 있다.
i에 대해 for문이 돌아가고 있고 i = 15가 되었다.
15가 현재까지 밝혀진(즉 15 미만의) 모든 소수를 하나씩 곱해보고 있다.
15에 2를 곱했더니 30이 되었고, 30에게 그의 spf가 2임을 알려주었다.

i에 대해 for문을 돌리면서 이러한 과정을 반복하면 모든 합성수의 spf를 얻을 수 있다.
소수는 "i = n이 될 때까지 아무도 자신의 spf를 안 알려준 경우"로 판정할 수 있다. 소수의 spf는 자기 자신이 된다.


여기서 두가지 의문점이 생긴다.

1. 설마 i 미만의 모든 소수를 다 곱해보진 않을텐데 어디서 끊는것인가?
2. i = 10에 3을 곱해서 30에게 spf가 3이라는 잘못된 정보를 줄 수도 있지 않은가?

이에 대한 해답이 바로 if i % p == 0: break이다.

i % p == 0은 i가 p의 배수라는 뜻이고, p가 i의 소인수라는 뜻이다.
그리고 처음으로 i % p == 0이 되는 p는 i의 최소 소인수이다.

i의 최소 소인수를 p_라고 할 때, i에 p_보다 더 큰 수를 곱해도 i의 최소 소인수는 여전히 p_이다. 따라서 p가 p_보다 더 커지는 경우 "i*p의 최소 소인수는 p입니다"라고 말할 수 없다.

p_ = 2인 i = 10을 예로 들면,

• spf[2*10] = 2 ← spf가 2인 수에 2를 곱하면 spf는 2가 된다.
• spf[3*10] = 3 ← spf가 2인 수에 3을 곱하면 spf는 3이 된다. 여전히 2이다.

따라서 p가 i의 최소 소인수일 때, 즉 p가 i의 소인수가 되는 순간 탈출하여 다음 i로 진행해야 한다.

동작방식 정리

(1) spf 리스트(각 수의 최소 소인수를 기록할 리스트)와 소수 리스트를 준비한다.
(2) i = 2~N for문을 돌린다.
(3) 만약 i의 spf가 기록되어있지 않다면 i는 소수이다. spf[i] = i로 기록하고, i를 소수 리스트에 추가한다.
(4-1) i 미만의 소수들 p에 대해 spf[i*p] = p로 기록한다.
(4-2) 단 i가 p의 배수라면 p의 for문을 중단하고 다음 i로 이동한다.

누락되는 숫자가 없음의 증명

일단 n이 소수인 경우, i = n이 될 때까지 n의 spf가 없을 것이다. 따라서 소수 판정이 가능하다.

n이 합성수인 경우, x * spf[n] = n에서 x는 무조건 존재한다. 또한, spf[x] >= spf[n]이다.

i = x일 때, i에 곱해지는 p는 spf[x] 이하이다. 즉, p = spf[n]이 되는 순간이 반드시 온다. 따라서 누락되는 숫자는 없다.

중복 판정이 없음의 증명

중복 판정(즉 spf 중복 기록)이 있으려면 같은 i*p값에 대해 spf[i*p] = p가 여러 번 실행되어야 한다.
(예를 들어 n=36이면 spf[12*3] = 3, spf[18*2] = 2)

일단, 여러 번 실행될 여지가 있으려면 i*p의 소인수가 최소 2가지 이상이어야 한다.

spf[i*p] = p에 서로 다른 두 개의 p값 p1, p2가 들어갈 수 있다고 가정해본다. (p1 < p2)

• spf[x1*p1] = p1 (x1 = i / p1)
• spf[x2*p2] = p2 (x2 = i / p2)

여기서 spf[x1] >= p1, spf[x2] >= p2여야 한다.
그런데 x2의 소인수에는 반드시 p1이 포함되어 있다. (x2 = i/p2 = (x1*p1)/p2)
즉 spf[x2] <= p1이고, p1 < p2라고 가정했으므로 모순을 일으킨다.

따라서 spf[i*p] = p에 서로 다른 두 개의 p값 p1, p2이 들어갈 수 없다.

N = int(input())
spf = [0]*(N+1)
prime_set = []
spf_updated = 0						# added code
for i in range(2, N+1):
    if not spf[i]:
        prime_set.append(i)
        spf[i] = i
        spf_updated += 1			# added code

    for p in prime_set:
        if i * p > N:
            break
        spf[i*p] = p
        spf_updated += 1			# added code
        if i % p == 0:
            break

print(spf_updated)					# added code

이 코드를 돌려보면 spf_updated의 값이 정확히 N-1이 나온다. (1이 제외됨)
즉 모든 수에 대해 spf를 단 한 번씩만 기록했음을 알 수 있다.

소인수분해

spf 리스트만 있으면 소인수분해는 매우 쉽다. n /= spf[n]를 반복해주면 된다.
최소 소인수를 반복해서 나누므로 무조건 오름차순으로 출력된다.

n = int(input())
while n > 1:
    print(spf[n])
    n //= spf[n]

C++ 코드

C++은 아직 익숙하지 않으니 이상한 점이 있으면 지적 부탁드립니다. 본문에 이상한 점이 있어도 지적 부탁드립니다. ll은 long long입니다.

vector<vector<ll>> linear_sieve(ll n){
  vector<ll> spf(n + 1);
  vector<ll> prime_set;

  for (ll i = 2; i <= n; i++){
    if (!spf[i]){
      prime_set.push_back(i);
      spf[i] = i;
    }

    for (auto p : prime_set){
      if (i * p > n) break;
      spf[i*p] = p;
      if (i % p == 0) break;
    }
  }

  return {prime_set, spf};
}

vector<ll> prime_factorization(ll n, vector<ll> &spf){
  vector<ll> ret;

  while (n > 1){
    ret.push_back(spf[n]);
    n /= spf[n];
  }
  return ret;
}

참고한 글

오일러의 체(Linear Sieve)로 O(logn) 소인수 분해 하기
https://nicotina04.tistory.com/155

Linear-sieve
https://ahgus89.github.io/algorithm/Linear-sieve/