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

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

 

문제

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

입력

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

출력

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

 

1번

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

tmp = []
for i in range(1, min(a,b) + 1):
    if a % i == 0 and b % i == 0:
        tmp.append(i)

print(max(tmp))
print(max(tmp) * (a // max(tmp)) * (b // max(tmp)))

 

for i in range(1, min(a,b) + 1):
    if a % i == 0 and b % i == 0:
        tmp.append(i)

1부터 입력받은 두수의 작은 수 + 1 까지의 반복문으로 두 수의 공약수를 tmp에 append 한다

 

print(max(tmp))

최대공약수 출력

공약수가 들어있는 tmp 에서 max 로 가장 큰 수를 출력한다

 

print(max(tmp) * (a // max(tmp)) * (b // max(tmp)))

최소공배수 출력 1

최대공약수 * (a // 최대공약수) * (b // 최대공약수)

 

print((a * b) // max(tmp))

최소공배수 출력 2

(a * b) // 최대공약수

 

 

2번

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

n, m = max(a, b), min(a, b)

while m > 0:
    n, m = m, n % m

print(n)
print((a * b) // n)

 

3번

def cal(n, m):
    if m == 0:
        return n
    if n % m == 0:
        return m
    return cal(m, n % m)

a, b = map(int, input().split())
n, m = max(a, b), min(a, b)

print(cal(n, m))
print((a * b) // cal(n, m))

 

2번과 3번 코드는 유클리드 호제법을 이용하였으며 반복문과 함수의 차이 이다

 

n, m = max(a, b), min(a, b)

입력받은 두 수 중에 큰수를 n 으로 작은수를 m 으로 정렬

 

알고리즘

1. 입력으로 두 수 n,m(n>m) 이 들어온다.
2. m이 0이라면, n을 출력하고 알고리즘을 종료한다.
3. n이 m으로 나누어 떨어지면, m을 출력하고 알고리즘을 종료한다.
4. 그렇지 않으면, n을 m으로 나눈 나머지를 새롭게 n에 대입하고, n과 m을 바꾸고 3번으로 돌아온다.

 

 

 

쉬운 방법

math 모듈에 최대공약수, 최소공배수 함수가 이미 있다

import math
a, b = map(int, input().split())
print(math.gcd(a,b))
print(math.lcm(a,b))

최대 공약수 : math.gcd(a, b)

최소 공배수 : math.lcm(a, b)

 

 

참고

유클리드 호제법

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95