정수론 (Number Theory)

정수론(Number Theory)은 수와 정수에 대한 속성과 구조를 연구하는 수학의 분야이다. 이론적으로 숫자와 관련된 다양한 패턴과 규칙을 이해하고, 숫자 간의 상호작용과 특성을 연구하는 분야이다.

Baekjoon - Number Theory

정수론의 주요 주제 및 개념은 다음과 같다:

---

Prime Numbers

Prime Number Test

소수 판별(Prime Number Test)은 주어진 수가 소수인지 아닌지를 확인하는 문제이다.

Baekjoon - Primality Test

알고리즘은 다음과 같다:

1. 1의 처리:
   먼저, n이 1인 경우를 확인한다. 1은 소수가 아니기 때문에, 함수는 False를 반환한다.

2. 범위 설정:
   그 다음, 2부터 n의 제곱근까지의 숫자 범위를 반복문을 통해 확인한다. 이 범위를 설정하는 이유는, 소수를 판별할 때 제곱근까지만 확인해도 충분하기 때문이다.

3. 나누어떨어지는지 확인: 반복문 내에서 n을 해당 숫자로 나누었을 때 나머지가 0인지를 확인한다. 만약 나머지가 0이라면, n은 그 숫자로 나누어 떨어진다는 의미이고, 이는 n이 소수가 아닌 것을 의미한다. 나머지가 0이면 함수는 즉시 False를 반환하고 실행을 종료한다.

4. 소수인 경우 반환:
   만약 위의 반복문을 모두 통과했다면, 즉, 어떤 숫자로도 n이 나누어떨어지지 않았다면, n은 소수이다. 함수는 이 경우 True를 반환한다.

def is_prime(n): # n은 자연수

    if n == 1:
        return False

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

    return True

answer = is_prime(50)

Eratosthenes' Sieve

에라토스테네스의 체(Eratosthenes' Sieve)는 소수를 찾는 방법 중 하나로, 고대 그리스의 수학자이자 천문학자인 에라토스테네스에 의해 개발되었다.

Baekjoon - Sieve Of Eratosthenes

알고리즘은 다음과 같다.

1. 먼저, 2부터 시작해서 소수의 여부를 판별할 범위 내의 모든 수를 나열한다.

2. 현재 숫자인 2를 소수로 인식하고, 2의 배수들을 모두 제거한다. (2를 제외한 2의 배수들은 소수가 아니다.)

3. 다음으로 남아있는 가장 작은 수를 소수로 인식하고, 해당 수의 배수들을 모두 제거한다.

4. 이전 단계를 반복하여 남아있는 수들을 소수로 인식하고, 해당 수의 배수들을 모두 제거한다.

5. 이 과정을 반복하면서 남아 있는 모든 수들은 소수이다.

def is_prime(n): # n은 자연수

    arr = [True] * (n + 1)
    arr[0] = False
    arr[1] = False

    for i in range(2, n + 1):
        if arr[i] == True:
            j = 2

            while (i * j) <= n:
                arr[i*j] = False 
                j += 1

    return arr

arr = is_prime(50)

---

Euler's Totient Function

오일러 파이(φ) 함수(Euler's Totient Function)는 양의 정수 n에 대해, n보다 작거나 같으면서 n과 서로소인 수의 개수를 반환한다.

Baekjoon - Euler Totient Function

Method 1

오일러 파이 함수의 표현식은 다음과 같다.

φ(n) = n (1 - 1/p1) (1 - 1/p2) ... (1 - 1/pk)
이때, p1, p2, ..., pk는 n의 서로 다른 소인수

def factorization(n): # n은 자연수
    d = 2 
    factorization = {}
    while d <= n: 
        if n % d == 0: 
            factorization[d] = factorization.get(d,0) + 1
            n = n / d 
        else: 
            d = d + 1
    return factorization
    
primes = factorization(990) # {2: 1, 3: 2, 5: 1, 11: 1}
    
def euler_phi(n): # n은 자연수
    primes = factorization(n)
    result = 1
    for key, value in primes.items():
        result *= key**(value-1) * (key-1)
    return result

result = euler_phi(990) # 240

Method 2

오일러 파이 함수의 또 다른 표현식은 다음과 같다.

φ(n) = p1^(a1 - 1) (p1 - 1) p2^(a2 - 1) (p2 - 1) ... pk^(ak - 1) (pk - 1)
이때, a1, a2, ..., ak는 각각 p1, p2, ..., pk의 거듭제곱에 해당하는 지수

def euler_phi(n): # n은 자연수
    primes = factorization(n)
    result = n
    for key in primes:
        result *= 1 - 1/key
    return int(result)

result = euler_phi(990) # 240

---

Euclidean Algorithm

유클리드 호제법(Euclidean Algorithm)은 두 개의 자연수의 최대공약수를 구하는 방법으로, 다음의 원리에 기반한다:

두 수 a와 b의 최대공약수는 b와 (a를 b로 나눈 나머지)의 최대공약수와 같다.

gcd(a, b) = gcd(b, a % b)

이 원리를 반복하여 나머지를 취하는 과정을 반복하다가, 나머지가 0이 되는 순간에 그때의 b가 두 수의 최대공약수가 된다.

Baekjoon - Euclidean Algorithm

def gcd(x, y):
    while(y):
        x, y = y, x % y
    return x

def lcm(x, y):
    return (x * y) // GCD(x, y)

result = gcd(10, 12) # 2
result = lcm(10, 12) # 60