[알고리즘] 최대공약수와 최소공배수

최대공약수

수론에서, 정수들의 공약수(common factor)는 동시에 그들 모두의 약수인 정수다. 적어도 하나가 0이 아닌 정수들의 최대공약수(greatest common factor, 약자 GCF)는 공약수 가운데 가장 큰 하나다.

1. Brute Force로 구하기

두 수중 작은 수를 고르고 1부터 작은 수까지 모든 수를 순회하면서 두 수를 동시에 나누어 떨어지게 하는 가장 큰 수를 구해 최대공약수 값을 얻는다. 

import sys
input = sys.stdin.readline

a,b = map(int,input().split())
min_num = min(a,b)


for i in range(min_num, 0, -1):
	if (a%i == 0 and b%i == 0):
    	answer = i
        break

print("gcd : ", answer)

2. 유클리드 호제법

유클리드 호제법의 원리

1. 두 양의 정수 a, b에 대해 (a > b) a를 b로 나눈 나머지를 r이라고 할 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 

2. 위 과정을 나머지가 0이 될 때까지 반복한다. 

3. 마지막으로 나누는 수로 사용된 값이 최대공약수이다. 

예시) a = 15,  b = 10

1. 15 % 10 = 5

    a = 10, b = 5

2. 10 % 5 = 0

    -> 나머지가 0이므로 최대공약수는 "5"

	a	b	r
초기	15	10
loop 1	15	10	5
loop 2	10	5	0

import sys
input = sys.stdin.readline

a,b = map(int,input().split())

def _gcd(a, b):
	while a % b != 0:
    	tmp = a%b
        a = b
        b = tmp
    return b
    
print(_gcd(a,b))

최대공약수

수론에서, 여러 개의 정수/다항식/환의 원소의 공배수(common multiple)는 그들 모두의 배수가 되는 정수/다항식/환의 원소이다. 최소공배수(least common multiple/ lowest common multiple, 약자 LCM)는 양의 공배수 가운데 가장 작은 하나이다.

공식 이용하기

LCM(a, b) = | a * b | / GCD(a, b)

import sys
input = sys.stdin.readline

a,b = map(int,input().split())

def _gcd(a, b):
	while a % b != 0:
    	tmp = a%b
        a = b
        b = tmp
    return b
    
def _lcm(a,b):
	return (abs(a*b) // gcd(a, b))

print(lcm(a, b))