[CS기초] 정수론(Number Theory)

정수론 개요

정수론은 정수의 성질 또는 정수가 등장하는 경우들을 연구하는 학문으로, 수학 체계에서 원점이자 정점 그 자체라고 할 수 있는데요. 기초 수준에서는 정수 그 자체보다는 자연수, 그 중에서도 소수를 중점적으로 다룹니다.

 

소수 (Prime Number)

1과 자기 자신으로만 나눠지는 수. 즉, 약수가 2개이며 2부터 N-1까지의 수로 나눠지지 않는 수를 말합니다.

소수 판정법

합성수(소수가 아닌 수)  N에서 1을 제외한 가장 작은 약수는 √N 이하라는. 그렇기 때문에 2부터 √N 이하의 자연수로 해당 수를 나눠보면 됩니다. 만약 도중에 나누어 떨어지게 되면 합성수, 아니라면 소수가 됩니다.

# 소수 판별 함수
def is_prime(number):
    if number == 1:
        return False
    i = 2
    while i * i <= number:
        if number % i == 0:
            return False
            break
        i += 1
    return True

에라토스테네스의 체

에라토스테네스의 체는 일정 범위의 소수 목록을 구하는 유명한 알고리즘입니다.

# 에라토스테네스의 체
def eratos(n):
    state = [True] * (n+1)
    if n == 1:
        return None
    i = 2   
    while i * i <= n:
        if not state[i]:
            i += 1
            continue
        j = i * i
        while j <= n:
            state[j] = False
            j += i
        i += 1
    primes = []
    for i in range(2, n+1):
        if state[i]:
            primes.append(i)
    return primes

소인수분해

합성수(소수가 아닌 수)를 소수의 곱으로 나타내는 것을 소인수분해라고 합니다.

# 소인수분해 함수
def prime_factorization(n):
    if n == 1:
        return
    
    i = 2
    while n > 1:
        if i * i > n:
            break
        while n % i == 0:
            n //= i
            print(i)
        i += 1

 

 

최대공약수 (GCD, Greatest Common Divisor)

약수 (Divisor)

먼저 약수는 어떤 수를 나누어 떨어지게 하는 수를 말합니다.

# 약수를 구하는 함수
def divisor(n):
    arr = []
    i = 1
    while i * i <= n:
        if n % i == 0:
            arr.append(i)
            if i * i != n:
                arr.append(n // i)
        i += 1
    return sorted(arr)

최대공약수 (GCD)

두 자연수의 공통된 약수 중 가장 큰 약수를 최대공약수라고 합니다.

# 최대공약수를 구하는 함수
def gcd(a, b):
    if a == 0:
        return b
    return gcd(b % a, a)

 

 

최소공배수 (LCM, Least Common Multiple)

어떤 정수의 몇 배가 되는 수를 배수(Multiple)라고 하는데, 두 자연수의 공통된 배수 중 가장 작은 배수를 최소공배수라고 합니다. 이때 a * b = gcd(a, b) * lcm(a, b) 라는 공식을 통해서 a와 b의 최소공배수를 구할 수 있습니다.

# 최소공배수를 구하는 함수. gcd 함수는 최대공약수 문단 참고
def lcm(a, b):
    return a // gcd(a, b) * b

 

 

연립합동방정식(Congruence Equation)

여러 개의 방정식이 주어졌을 때, 이를 동시에 만족하는 해를 구하는 문제를 연립합동방정식이라고 합니다.

# m으로 나눈 나머지가 x 이면서,
# n으로 나눈 나머지가 y 이면서,
# n과 m의 최소공배수와 같거나 작은 최초의 수를 구하는 함수
# (lcm 함수는 최소공배수 문단 참고)
def func(m, n, x, y):
    if x == m:
        x = 0
    if y == n:
        y = 0
    
    max_limit = lcm(m, n)
    i = x
    while i <= max_limit:
        if i != 0 and i % n == y:
                return i
        i += m
    return -1

 

 

이항 계수 (Binomial Coefficient)

주어진 집합에서 원하는 개수만큼 뽑았을 때 모든 조합에 대한 경우의 수를 이항 계수라고 합니다.

조합과 순열

• 조합 (Combination) : 순서를 고려하지 않고 n개에서 k개를 뽑는 경우의 수
  • 공식 : nCk = n! / ( (n-k)! * k! )
• 순열 (Permutation) : 순서를 고려하여 n개에서 k개를 뽑는 경우의 수
  • 공식 : nPk = n! / (n-k)!

# 이항계수를 구하는 함수. (이항계수 공식 구현)
def nck(n, k):
    result = 1
    a, b, c = 1, 1, 1
    while a <= n:
        result *= a
        a += 1
    while b <= n-k:
        result //= b
        b += 1
    while c <= k:
        result //= c
        c += 1
    return result

# 이항 계수 (N K) 를 10007로 나눈 나머지를 구하는 함수. (DP 이용)
n, k = map(int, input().split())
dp = [[0] * (n+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
    dp[i][0], dp[i][i] = 1, 1
    for j in range(1, n+1):
        dp[i][j] = (dp[i-1][j] + dp[i-1][j-1]) % 10007
print(dp[n][k])

 

 

참고 자료

BaaaaaaaarkingDog, "[실전 알고리즘] 0x12강 - 수학", 2021.06.30,
https://blog.encrypted.gg/983