최대공약수

최대공약수 GCD(Greatest Common Divisor): 두 자연수의 공통된 약수 중 가장 큰 수를 의미한다.

최소공배수

최소공배수 LCM(Least Common Multiple): 최소공배수는 두 자연수의 공통된 배수 중 가장 작은 수를 의미한다.

유클리드 호제법

최대공약수(GCD)를 구하는 알고리즘이다.
그림과 같이 서로를 번갈아가며 나머지만 남기고 한쪽이 0이 되면 남은 값을 반환한다.

1. 입력으로 두 수 m,n(m>n)이 들어온다.
2. n이 0이라면, m을 출력하고 알고리즘을 종료한다.
3. m이 n으로 나누어 떨어지면, n을 출력하고 알고리즘을 종료한다.
4. 그렇지 않으면, m을 n으로 나눈 나머지를 새롭게 m에 대입하고, m과 n을 바꾸고 3번으로 돌아온다.

파이썬 코드

def gcd(m,n):
	if m < n:
		m, n = n, m
	if n == 0:
		return m
    if m % n == 0:
		return n
	else:
		return gcd(n, m%n)

최대공약수와 최소공배수의 관계

두 자연수의 곱 = 최대공약수 * 최소공배수