백준 - 2609 (Python) - 최대공약수와 최소공배수

박준영·2021년 7월 10일
0
post-thumbnail

최대공약수와 최소공배수


문제

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


입력

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


출력

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


코드

유클리드 호제법 -> 포스트 참고하기
: 최대공약수를 구하는 알고리즘 중 하나이다.
두 자연수 a,b에서(a>b) a를 b로 나눈 나머지를 r이라고 하면 a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
때문에 a에 b를 넣고, b에 r을 넣고 나머지가 0일 때 까지 반복한다.
이때 a값이 두 수의 최대공약수이다.
최소공배수는 주어진 두 수를 곱해서 최대공약수로 나누면 구할 수 있다.

  • 풀이


a, b = map(int, input().split())
 
def gcd(a, b): # 최대공약수
    while b != 0:
        c = a%b
        a = b
        b = c
    return a
 
def lcm(a,b): # 최소공배수
    baesu = (a*b) / gcd(a,b)
    return baesu
 
print(gcd(a,b))
print(int(lcm(a,b)))

0개의 댓글

관련 채용 정보