[알고리즘/Python] 최대공약수, 최소공배수

최대 공약수

최대 공약수란, 숫자 a, b가 주어졌을 떄, 공통되는 약수 중에서 최대 값을 의미한다.

최대 공약수 구하기.

1. a,b 약수를 모두 구해서 공통 되는 약수 중에서 가장 큰 값을 찾는 방법
   • 찾지 않아도 되는 약수 까지 구해야해서 효율적이지는 않다.
2. 유클리드 호제법
   • 유클리드 호제법이란 숫자 a,b가 있을 경우 a를 b로 나눈 나머지와 b의 최대 공약수는 a와 b의 최대 공약수가 같다는 것을 의미한다.
   • 그럼, 계속해서 a 를 b로 나누어서 b를 a에 나눈 나머지를 b 에 대입시켜서 b 가 0이 될때 까지 반복을
     하면, 남는 a 값이 바로 최대 공약수 이다.
     데이터 베이스 사용을 위해 USE를 사용하여 데이터베이스를 선택할 수 있습니다.

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

최소공배수

서로 다른 수 a,b의 배수 중에서 공통되는 배수 중에 가장 작은 값을 의미한다.

최소공배수는 a,b의 곱을 a,b의 최대 공약수로 나누면 나오게 된다.

import sys
def gcd(a, b):
    while b>0:
    	a, b = b, a%b
    return a

def lcd(a, b):
    return a * b / gcd(a, b)