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

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

 

예제 입력 1

24 18

예제 출력 1 

6
72

 

---

풀이

최대공약수(GCD) = 약수 중 공통이며 가장 큰 수

최소공배수(LCM) = 각각의 배수 중 공통이며 가장 작은 수

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

# 최대 공약수
a_gcd = [i for i in range(1, a+1) if a % i == 0]
b_gcd = [i for i in range(1, b+1) if b % i == 0]

gcd = 0
for i in range(len(a_gcd)):
    for j in range(len(b_gcd)):
        if a_gcd[i] == b_gcd[j]:
            gcd = a_gcd[i]
print(gcd)

# 최소 공배수
lcm = 0

i = 1
while True:
    if i % a == 0 and i % b == 0:
        print(i)
        break

    i += 1

이렇게 풀었는데 자꾸 시간초과가 발생한다.

 

 

또 다른 풀이

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

# 최대 공약수
for i in range(min(a, b), 0, -1):
    if a % i == 0 and b % i == 0:
        print(i)
        break

# 최소 공배수

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

1. 최대 공약수

a, b 중 작은 숫자부터 1까지 역행하며 for문을 실행한다.

만약 a % i와 b % i 가 모두 0이라면, 이때 i가 최대 공약수이다.

 

2. 최소 공배수

a, b 중 큰 숫자부터 a*b 까지 for문을 실행시킨다.

이때, i % a 와 i % b 가 모두 0이면, i는 최소 공배수가 된다.

=> 처음에 a % i, b % i 로 구현했는데 이렇게 되면 2와 5를 구했을 경우 정답인 10이 아닌 1이 출력된다.

 

 

유클리드 호제법 사용

'x, y의 최대 공약수는 y, r의 최대 공약수와 같다'는 원리를 이용 ( x%y = r ). 이때 r = x % y

 

ex) a = 10, b = 12

      10 % 12 = 10

      12 % 10 = 2

       10 % 2 = 0

=> 나머지 값이 0일때의 b 값이 최대 공약수

 

# 유클리드 호제법 사용
def GCD(a, b):
    while b > 0:
        a, b = b, a % b

    return a


def LCM(a, b):
    lcm = (a * b) // GCD(a, b)
    return lcm


print(GCD(a, b))
print(LCM(a, b))

 

 

 

 

 

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

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