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

문제

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

입력

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

출력

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

---

풀이

[기존 풀이]

a, b = map(int, input().split())
answer1 = 0
answer2 = 0

if(a >= b):
    n = a
else:
    n = b

for i in range(0, n+1):
    if(i == 0):
        answer1 = 0
        answer2 = 0
    elif(a%i == 0 and b%i == 0):
        answer1 = i
        answer2 = a//answer1 * b//answer1 * answer1
print(answer1)
print(answer2)

 

[유클리드 호제법]

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)


if(a == 0 and b == 0):
    print(0)
    print(0)
elif(a > b):
    print(gcd(a, b))
    print(lcm(a, b))
else:
    print(gcd(b, a))
    print(lcm(b, a))

 

 

참고🐣

유클리드 호제법

숫자 a, b가 있을 때, a를 b로 나눈 나머지와 b의 최대 공약수는 a와 b의 최대 공약수가 같다는 것을 의미

 

[최대공약수]

b를 a에 나눈 나머지를 b에 대입하여 b가 0이 될 때까지 반복하면 남는 a값

 

추가 참고 자료: https://codingpractices.tistory.com/34#google_vignette

 

문제 출처

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

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