정수론(Number Theory)

정수론이란?

• 정수의 성질을 다루는 수학 이론
• 알고리즘 문제에서 자주 쓰이는 기본 연산과 개념들을 포함
• 자주 사용되는 개념:
  • 약수, 배수
  • 최대공약수(GCD), 최소공배수(LCM)
  • 소수, 소수 판별
  • 모듈(mod) 연산
  • 소인수 분해

---

약수 구하기

def get_divisors(n):
    result = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            result.append(i)
            if i != n // i:
                result.append(n // i)
    return sorted(result)

• 시간 복잡도: O(√N)

---

최대공약수(GCD), 최소공배수(LCM)

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

• 시간 복잡도: O(log N)
• 유클리드 호제법 기반

---

소수 판별

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

• 시간 복잡도: O(√N)

---

에라토스테네스의 체

def sieve(n):
    prime = [True] * (n + 1)
    prime[0] = prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if prime[i]:
            for j in range(i*i, n+1, i):
                prime[j] = False
    return [i for i in range(n + 1) if prime[i]]

• 시간 복잡도: O(N log log N)
• 1부터 N까지 모든 소수 구할 때 사용

---

모듈(mod) 연산 법칙

연산	공식
덧셈	(a + b) % c = ((a % c) + (b % c)) % c
곱셈	(a b) % c = ((a % c) (b % c)) % c
뺄셈	(a - b) % c = ((a % c) - (b % c) + c) % c

• 오버플로우 방지와 수식 정리에 유용함

---

소인수 분해

def prime_factors(n):
    factors = []
    i = 2
    while i * i <= n:
        while n % i == 0:
            factors.append(i)
            n //= i
        i += 1
    if n > 1:
        factors.append(n)
    return factors

• 시간 복잡도: O(√N)
• 어떤 정수를 소수의 곱으로 표현

---

시간 복잡도 정리

연산	시간 복잡도
약수 구하기	O(√N)
GCD (유클리드)	O(log N)
소수 판별	O(√N)
소수 전체 구하기 (에라토스테네스)	O(N log log N)
소인수 분해	O(√N)

---

핵심 요약

• 약수, 배수, GCD/LCM, 소수는 모든 수학/수열 문제의 기본 도구
• 에라토스테네스의 체는 소수 리스트 생성 최적화 알고리즘
• 모듈 연산 성질은 곱셈/덧셈/뺄셈의 형태 유지에 필수
• 소인수 분해는 소수 조건 탐색, 조합 문제, 약수 개수 구하기 등에서 자주 등장
• 정수론은 탐색 + 수학 + 최적화 문제에서 자주 활용되는 핵심 주제