소인수분해 (Prime Factorization)

정의

소인수분해 (Prime Factorization) 는 양의 정수 N을 소수들의 곱으로 유일하게 나타내는 것. N = p₁^a₁ · p₂^a₂ · … · pₖ^aₖ. 시행 나눗셈 O(√N), 에라토스테네스 체로 O(log N) 전처리, Pollard rho O(N^1/4) 가 대표적.

문제 상황과 동기

정수 N (10^12 이하) 의 소인수를 전부 구하라.

• naive (2..N-1 순회): O(N). N=10^12 면 timeout.
• 시행 나눗셈 (Trial Division): 2부터 √N 까지 나누기. O(√N). N=10^12 면 10^6.
• 체로 빠른 분해: N 이하 소수 미리 체로 구해 두면, O(π(√N)) ≈ O(√N / log N).
• Pollard rho: 확률적 O(N^1/4). N=10^18 도 몇 초 안에 분해.

핵심 통찰: N 이 합성수면 √N 이하 소인수가 반드시 하나 존재. 작은 소인수부터 제거하면 나머지는 큰 소수 하나만 남음.

시각화

핵심 아이디어

시행 나눗셈

N 을 2, 3, 5, 7, ... 순서대로 나눔.
나누어떨어지면 그 소수를 기록하고, N /= p.
√N 이하 소인수 전부 제거 후, N > 1 이면 N 자체가 소수.

체로 빠른 분해

N 이하 소수를 에라토스테네스 체로 미리 구해 두면,
소인수분해 시 체에서 뽑은 소수만 시도 → O(π(√N)).

Pollard rho

GCD 기반 확률적 방법. f(x) = x² + c (mod N) 사이클 찾기.

x₀ = 2, y₀ = 2
repeat:
    x = f(x), y = f(f(y))
    d = gcd(|x - y|, N)
    if 1 < d < N: return d  // 비자명 약수
재귀적으로 d, N/d 분해.

알고리즘

Trial Division (O(√N))

factorize(N):
    res = []
    for p = 2..sqrt(N):
        if p * p > N: break
        while N % p == 0:
            res.append(p)
            N /= p
    if N > 1: res.append(N)
    return res

Optimized Trial (6k±1)

factorize(N):
    res = []
    for p in [2, 3]:
        while N % p == 0:
            res.append(p)
            N /= p
    i = 5
    while i * i <= N:
        for p in [i, i+2]:  // 6k-1, 6k+1
            while N % p == 0:
                res.append(p)
                N /= p
        i += 6
    if N > 1: res.append(N)
    return res

Pollard rho (확률적, 큰 N)

pollard_rho(N):
    if is_prime(N): return [N]
    if N % 2 == 0:
        return [2] + factorize(N / 2)
    x, y, d = 2, 2, 1
    f = lambda x: (x*x + 1) % N
    while d == 1:
        x = f(x)
        y = f(f(y))
        d = gcd(abs(x - y), N)
    if d == N: retry with different c
    return factorize(d) + factorize(N / d)

구현

// Trial division O(√N), 6k±1 최적화
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
​
vector<ll> factorize(ll n) {
  vector<ll> res;
  for (ll p : {2, 3}) {
      while (n % p == 0) {
          res.push_back(p);
          n /= p;
      }
  }
  for (ll i = 5; i * i <= n; i += 6) {
      for (ll p : {i, i + 2}) {
          while (n % p == 0) {
              res.push_back(p);
              n /= p;
          }
      }
  }
  if (n > 1) res.push_back(n);
  return res;
}
​
int main() {
  ll n; cin >> n;
  auto factors = factorize(n);
  for (ll p : factors) cout << p << " ";
  cout << "\n";
}

# Trial division, 6k±1
def factorize(n):
  res = []
  for p in [2, 3]:
      while n % p == 0:
          res.append(p)
          n //= p
  i = 5
  while i * i <= n:
      for p in [i, i + 2]:
          while n % p == 0:
              res.append(p)
              n //= p
      i += 6
  if n > 1:
      res.append(n)
  return res
​
import sys
input = sys.stdin.readline
n = int(input())
factors = factorize(n)
print(" ".join(map(str, factors)))

// Trial division, ArrayList<Long>
import java.util.*;
import java.io.*;
public class Main {
  static List<Long> factorize(long n) {
      List<Long> res = new ArrayList<>();
      for (long p : new long[]{2, 3}) {
          while (n % p == 0) {
              res.add(p);
              n /= p;
          }
      }
      for (long i = 5; i * i <= n; i += 6) {
          for (long p : new long[]{i, i + 2}) {
              while (n % p == 0) {
                  res.add(p);
                  n /= p;
              }
          }
      }
      if (n > 1) res.add(n);
      return res;
  }
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      long n = Long.parseLong(br.readLine());
      List<Long> factors = factorize(n);
      StringBuilder sb = new StringBuilder();
      for (long p : factors) sb.append(p).append(' ');
      System.out.println(sb);
  }
}

60

2 2 3 5

1000000007

1000000007

복잡도

변형

함정

1. √N 이후 N > 1

for (ll i = 2; i * i <= n; i++) ...
if (n > 1) res.push_back(n);  // 빼먹으면 큰 소인수 누락

2. long long 범위

N=10^18 의 소인수는 10^9 초과 가능. int 로 저장하면 오버플로우.

3. Pollard rho 무한 루프

gcd(|x-y|, N) 가 계속 1 또는 N 이면 c 를 바꿔 재시도. 보통 c=1, 2, … 순회.

4. 중복 소인수

N=12=2²·3. 결과는 [2, 2, 3]. map<ll, int> 로 (소인수, 지수) 저장도 가능.

BOJ 연습 문제

참고

• 소수 판정
• 유클리드 호제법
• 에라토스테네스의 체