백준 [2609.최대공약수와 최소공배수] | Python

✏️ 문제

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

 

✏️ 풀이방법

- 최대공약수('GCD':Greatest Common Divison)는 두 개 이상의 수의 공통된 약수 중 가장 큰 약수를 말하고, 최소공배수('LCM':Least Common Multiple)는 두 개 이상의 수의 공통된 배수 중 가장 작은 수를 말한다. 

- 다음 그림처럼 소인수분해를 통해서 최대공약수와 최소공배수를 구할 수 있다.

1. 최대공약수(gcd)는 두 자연수 a,b를 공통으로 나누는 수(i)를 찾아 리스트(gcd)에 담아서 가장 큰 값을 출력한다.

2. 최소공배수(lcm)는 두 자연수 a,b를 최대공약수로 나누고 남은 나머지들의 곱에 최대공약수를 곱한다.

   즉, 두 자연수 a,b의 곱을 최대공약수로 나누면 된다.

 

 

📌 코드

a,b = map(int,input().split())
gcd = []
if a == b: #a와b가 서로 같은 경우 최대공약수와 최소공배수는 자기자신
    print(a)
    print(a)
else:
    i = 1
    while True:
        if a % i == 0 and b % i == 0:
            gcd.append(i)
        i += 1
        if i > a or i > b:
            break
    print(max(gcd))
    lcm = a * b // max(gcd)
    #lcm = (a//max(gcd))*(b//max(gcd))*max(gcd)
    print(lcm)

 

 

📌 결과

#입력
24 18

#출력
6
72

 

 

 

🔎 다른풀이1.

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

# 최대공약수
# a & b의 최대 공약수는 b & a를 b로 나눈 나머지의 최대 공약수
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

# 최소공배수 
# a와 b의 곱을 a와 b의 최대 공약수로 나눈 값
def lcm(a, b):
    return a * b // gcd(a, b)


print(gcd(a, b))
print(lcm(a, b))

- https://rladuddms.tistory.com/107

-  유클리드 호제법으로 풀이

 

 

🔎 다른풀이2.

import math

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

print(math.gcd(a,b))
print(math.lcm(a,b))

- 파이썬에 내장된 math모듈 활용하기

 

📝 메모

- 유클리드 호제법