풀이_2609.md

😐 백준 2609번 (최대공약수와 최소공배수)

• Date : 2021.03.05(금)
• Time : 15분

문제

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

입력

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

출력

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

math 모듈을 이용한 풀이

from math import gcd
def less(a,b) :
    return a*b // gcd(a,b)
A,B = map(int,input().split())
print(gcd(A,B),less(A,B))

: 파이썬 내장함수 math 모듈에 있는 gcd 함수를 이용해서 최대 공약수는 바로 구할 수 있다. 그리고 최소 공배수는 A,B 곱 나누기 A,B의 최대공약수로 표현할 수 있다.

유클리드 호제법을 이용한 풀이

def gcd(a,b):
    if a%b == 0 :
        return b
    elif b == 0 :
        return a
    else :
        return gcd(b,a%b)

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

A,B = map(int,input().split())
print(gcd(A,B),less(A,B))

: 유클리드 호제법은 a, b의 최대공약수와 b, r(a%b의 나머지) 의 최대공약수가 같다는 성질을 이용한 풀이이다. 계속 계산을 반복해 나머지가 0이 될 때까지 계산한다.