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

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

문제

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

입력

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

출력

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

풀이 (시간초과)

가장 처음에 생각한 풀이
그냥 간단하게 생각한 것 -> 시간초과 난다...

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

if b > a:
    a, b = b, a
#a>b

gcd = 0
lcm = 0
for i in range(2, b+1): #2~b까지 돈다
    if b % i == 0 and a % i == 0:
        gcd = i
print(gcd)

lcm = a * b // gcd
print(lcm)

맞는 풀이

def gcd_fun(x,y):
    while y != 0:
        r = x % y
        x, y = y, r
    return x #헷갈리지 마 y가 아니라 x를 리턴해야돼

a, b = map(int, input().split(" "))
if b > a:
    a, b = b, a
#a>b

gcd = gcd_fun(a,b)
print(gcd)

lcm = a * b // gcd
print(lcm)

설명

📌 유클리드 호제법을 이용하여 최대공약수를 구함
📌 최소공배수는 두 수의 곱을 최대공약수로 나눈 값

최대공약수 구하기

a > b 조건이 전제조건.
a = 10, b = 4라고 해보자
10 % 4 = 2
a에 4 대입, b에 2 대입
4 % 2 = 0
나머지가 0이 되었다 -> 이 때 b의 값(2)이 최대공약수!

파이썬에 내장되어 있는 함수 gcd , lcm 사용

(Greatest Common Divisor) (Least Common Multiple)

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