최대공약수(GCD)와 최소공배수(LCM)

최대공약수(Greatest Common Divisor)

• 두 개 이상의 정수 중에서 공통된 약수 중 가장 큰 수

예시) 12와 18의 최대공약수는 6이다. 이는 12와 18의 공통된 약수 중에서 가장 큰 수인 6이기 때문이다.

최대공약수는 정수의 약수 중에서 가장 큰 공통된 약수를 구하는 것이 가능하다. 이때, 유클리드 호제법을 사용할 수 있다. 이 방법은 큰 수를 작은 수로 나누어서 나머지를 구하는 과정을 반복하여, 나머지가 0이 되는 순간 나누는 수가 최대공약수가 된다. 예를 들어, 84와 60의 최대공약수를 구한다면 다음과 같은 과정을 거친다.

84를 60으로 나누면 나머지는 24
60을 24로 나누면 나머지는 12
24를 12로 나누면 나머지는 0
따라서, 12가 최대공약수가 된다.

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

a = int(input("첫 번째 숫자를 입력하세요: "))
b = int(input("두 번째 숫자를 입력하세요: "))

print(f"{a}와 {b}의 공약수: ", end="")
for i in range(1, gcd(a, b)+1):
    if a % i == 0 and b % i == 0:
        print(i, end=" ")

print(f"\n{a}와 {b}의 최대공약수: {gcd(a, b)}")

# 유클리드 호제법
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

a = int(input("첫 번째 숫자를 입력하세요: "))
b = int(input("두 번째 숫자를 입력하세요: "))

print(f"{a}와 {b}의 최대공약수: {gcd(a, b)}")

---

최소공배수(Least Common Multiple)

• 주어진 두 수의 공통된 배수 중에서 가장 작은 수

2와 3의 최소공배수는 6이며, 4와 6의 최소공배수는 12이다.

최소공배수는 최대공약수를 이용해서 구할 수 있다. 두 수 a, b의 최소공배수는 다음과 같이 구할 수 있다.

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

즉, 두 수의 곱을 최대공약수로 나누어 주면 최소공배수를 구할 수 있다.

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

a = int(input("첫 번째 숫자를 입력하세요: "))
b = int(input("두 번째 숫자를 입력하세요: "))

# 공약수 출력
print(f"{a}와 {b}의 공약수: ", end="")
for i in range(1, gcd(a, b)+1):
    if a % i == 0 and b % i == 0:
        print(i, end=" ")

# 최대공약수 출력
print(f"\n{a}와 {b}의 최대공약수: {gcd(a, b)}")

# 최소공배수 계산 및 출력
lcm = (a * b) // gcd(a, b)
print(f"{a}와 {b}의 최소공배수: {lcm}")