[백준/Python]약수, 배수와 소수

문제를 풀다보면 자주 출제되는 개념이 있다.
약수, 배수, 소수 + 최대공약수, 최소공배수, 소인수분해...
'안다'고 해서 끝나는게 아니라 이해 → 풀이 → 최적화 까지 가야하므로 헷갈릴때가 많다.
이참에 정리해두려고 한다.

문제

https://www.acmicpc.net/step/10

 

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

약수: 어떤 수를 나누었을때 나누어 떨어지는 수.
최대공약수는 두 수의 공통된 약수 중 가장 큰 수를 말한다.

 

math.gcd()

Python에는 math모듈이 있는데, 이 모듈의 gcd()함수를 사용하면 최대공약수를 쉽게 구할 수 있다.

import math

def gcd(a, b):
    return math.gcd(a, b)

print(gcd(24, 36))  # 12

하지만 자주 사용하는 방법은 아니다.

 

유클리드 호제법

주로 쓰는 방식이다.

 

두 수 a, b가 있을때 a를 b로 나눈 나머지를 r이라 한다면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 원리다.
a % b == r일때, gcd(a, b) == gcd(b, r)라는 소리다.

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

print(gcd(24, 36))  # 12

a, b를 입력받은 후 a를 b로, b를 a%b(r)로 계속 재할당한다.
재귀적으로 반복하다 b가 0이 되는순간 a를 반환한다.
더 큰 수를 a로 지정해주고 실행해도 되지만 딱히 그럴 필요는 없다.

# a % b = r
24 % 36 = 24
36 % 24 = 12
24 % 12 = 0  # 여기서 a, b = 12, 0이 되므로 반복문 종료.

---

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

배수: 어떤 수에 정수를 곱하여 얻을 수 있는 수.
최대공배수는 두 수의 공통된 배수 중 가장 작은 수.

최대공배수를 구하는 방식은 간단한데, 두 수의 곱을 최대공약수로 나누어 구하면 된다.

 

최대공약수 사용하기

import math

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

print(lcm(24, 36))  # 72

---

소수 (Prime Number)

: 1과 자기 자신 이외의 약수를 갖지 않는 수.

여기서 에라토스테네스의 체 개념이 쓰인다.

 

에라토스테네스의 체

2부터 시작하여 배수들을 제거해나가는 방식이다.

 

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False

    for i in range(2, int(n ** 0.5) + 1):
        if primes[i]:
            for j in range(i * i, n + 1, i):
                primes[j] = False

    return [i for i in range(2, n + 1) if primes[i]]

print(sieve_of_eratosthenes(30))  # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

인덱스의 범위를 0부터 n까지로 잡아놔야하기 때문에, [True]의 갯수를 (n+1)만큼으로 설정한다.

그 다음 2부터 n의 제곱근까지 순회한다.
만약 primes[i]가 True라면 i에 해당하는 수의 배수들을 모두 False로 설정한다.
체로 걸러주는거다.

 

여기서 n의 제곱근까지만 순회하는 이유는 다음과 같다.
어떤 합성수 x가 있다고 가정해보자.
이 수는 두개의 소수 a, b의 곱으로 표현할 수 있다.
즉 x = a * b인 셈이다. (모든 합성수가 꼭 두개의 소수 곱으로 표현할 수 있는건 아니지만 그렇다 치자.)
여기서 a나 b 둘 중 하나는 제곱근보다 작아야한다.
만약 둘 다 제곱근보다 클 경우, a * b > x가 되는셈이기 때문이다.

따라서 a, b 중 제곱근보다 작은 수는 무조건 존재하고, 그 수의 배수 또한 제거할 수 있다.

에라토스테네스의 체에서 "합성수 = 두 소수의 곱"으로 가정하는 이유는 다음과 같다.

1. 모든 합성수는 소수의 곱으로 표현될 수 있다. (소수의 정의에 따라)
2. 어떤 합성수가 두 개의 소수의 곱으로 표현되지 않는다면, 그 합성수는 반드시 적어도 하나의 제곱수(square number)를 인수로 가진다.

---

소인수분해

: 자연수를 소수의 곱으로 나타내는 것.
예를들어 12 를 소인수분해하면 2 x 2 x 3 이 된다.

 

특징

• 모든 자연수는 소수의 곱으로 유일하게 표현될 수 있다. (산술의 기본 정리)
• 소인수분해의 결과는 오름차순으로 정렬된 소수의 곱이다.

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

print(prime_factorization(12))  # [2, 2, 3]
print(prime_factorization(360))  # [2, 2, 2, 3, 3, 5]

순회가 끝난 뒤 n이 1보다 크다면 n 자체가 소수라는 것이므로, n을 append한다.