최소공배수와 최대공약수

최소공배수(Least Common Multiple)

• 두 수 이상의 수들의 공통인 배수 중 가장 작은 수.

주어진 수 중 가장 큰 수부터 모두 곱한 수까지 반복한다. 1 씩 더했을 때 모두 나누어 떨어지는 첫 번째 수가 가장 작은 공배수이므로 최소공배수다.
이 때 반복문을 끝까지 돈다면 a*b가 최소공배수다.

for i in range(max(a, b), (a*b)+1):
	if i % a == 0 and i % b == 0:
    	print(i)
        break

최대공약수(Greatest Common Divisor)

• 두 수 이상의 수들의 공통인 약수 중 가장 큰 수.

주어진 수 중에 가장 작은 숫자부터 1 씩 줄이면서 모두 나누어 떨어지는 첫 번째 수가 가장 큰 공약수이므로 최대공약수이다.

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

유클리드 호제법

a, b 의 최대공약수 == b, r 의 최대공약수 ( a % b == r)

a를 b로 나눈 나머지를 b에, b를 a에 대입시켜서 b == 0이 될 때까지 반복을 하면 남은 a값이 바로 최대공약수를 임을 의미한다.

# 최대공약수
def gcd (a, b):
    while b:
        a,b = b, a%b
    return a

# 최소공배수
def lcm (a,b):
    return a * b / gcd(a,b)

math 모듈 이용하기

근데 파이썬엔 이미 만들어져 있는걸...

import math

print(math.gcd(20, 45))
print(math.lcm(10, 20))