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

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

문제

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

입력

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

출력

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

 

과정

• 유클리드 호제법을 사용하여 최대공약수를 구해준다.
• 유클리드 호제법이란
  숫자 a, b가 있을 때, a를 b로 나눈 나머지와 b 의최대 공약수 는 a 와 b 의 최대 공약수 가 같다는 것을 의미한다.
  그럼, 계속해서 a 를 b로 나누어서 b를 a에 나눈 나머지를 b 에 대입시켜서 b 가 0이 될때 까지 반복을
  하면, 남는 a 값이 바로 최대 공약수 이다.
• 최대공약수를 이용해 최소공배수를 구한다.
  최소공배수는 a, b의 곱을 a, b의 최대 공약수로 나누면 나오게 된다.

예제 입력

24 18

예제 출력

6
72

 

풀이

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

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

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

 

한 줄씩 해석해보기

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

• 정수 두 개를 입력 받는다.

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

• 유클리드 호제법을 이용해 풀어준다.
• a & b의 최대 공약수는 b & a를 b로 나눈 나머지의 최대 공약수와 같다.
  단, a > b이어야만 a를 b로 나눈 나머지를 구할 수 있다.

def lcm(a, b):
    return a * b // gcd(a, b)

• 최소공배수는 a와 b의 곱을 a와 b의 최대 공약수로 나눈 값

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

• 값을 출력해준다.

 

파이썬 모듈을 이용한 풀이

import math

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

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

• 내장함수 math를 이용하면 최대공약수와 최대공배수를 바로 구할 수 있다.