[Python-알고리즘] 소수론

정수론 (Number Theory) 정리 및 응용 문제

---

1. 정수론이란?

정수론은 정수와 관련된 수학적 성질을 다루는 분야로, 알고리즘 문제 해결에서 중요한 기반이 됩니다.
소수, 최대공약수, 최소공배수, 약수, 배수, 합동(mod) 연산, 유클리드 호제법, 페르마의 소정리 등이 주요 개념입니다.

---

2. 주요 개념 요약

• 소수 (Prime Number): 1과 자기 자신만을 약수로 가지는 자연수
• 최대공약수 (GCD): 두 수가 공통으로 가지는 약수 중 가장 큰 수
• 최소공배수 (LCM): 두 수의 공통 배수 중 가장 작은 수
• 유클리드 호제법: GCD를 빠르게 구하는 알고리즘, a % b를 반복
• 에라토스테네스의 체: 특정 범위의 모든 소수를 구하는 효율적인 방법

---

3. 응용 문제 및 코드 (주석 포함)

1) 소수 판별

# 소수인지 판별하는 함수
def is_prime(n):
    if n < 2:
        return False  # 2보다 작은 수는 소수가 아님
    for i in range(2, int(n**0.5) + 1):  # 2부터 √n까지 반복
        if n % i == 0:
            return False  # 나누어 떨어지면 소수가 아님
    return True

# 테스트
print(is_prime(17))  # True (소수)

2) 최대공약수와 최소공배수 (유클리드 호제법)

# 최대공약수(GCD)를 구하는 함수
def gcd(a, b):
    while b:
        a, b = b, a % b  # 유클리드 알고리즘
    return a

# 최소공배수(LCM)를 구하는 함수
def lcm(a, b):
    return a * b // gcd(a, b)  # a와 b의 곱을 GCD로 나눈 값

# 테스트
print(gcd(24, 36))  # 12
print(lcm(24, 36))  # 72

3) 에라토스테네스의 체로 소수 목록 구하기

# n 이하의 모든 소수를 구하는 함수 (에라토스테네스의 체)
def sieve(n):
    is_prime = [True] * (n + 1)  # 모든 수를 소수로 초기화
    is_prime[0], is_prime[1] = False, False  # 0과 1은 소수가 아님

    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):  # i의 배수들을 제거
                is_prime[j] = False

    return [i for i, val in enumerate(is_prime) if val]  # 소수 리스트 반환

# 테스트
print(sieve(30))  # 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

---

4. 시간 복잡도

• 소수 판별: O(√n)
• GCD (유클리드 호제법): O(log(min(a, b)))
• 에라토스테네스의 체: O(n log log n)

---

5. 실전 팁

• 정수론 문제는 대부분 시간 초과가 날 수 있으므로 빠른 알고리즘을 기억해두자.
• mod 연산을 많이 활용하며, (a + b) % m = ((a % m) + (b % m)) % m 을 기억하자.
• 특히 소수판별, GCD/LCM, 소인수분해는 기본 중의 기본!