1-7목표. 백준 2609번 최대공약수와 최소공배수

오늘의 문제~~~

 

최대공약수(Greatest Common Divisor)와 최소공배수(Least Common Multiple)

 

*유클리드 알고리즘

 -자연수 2개의 최대공약수를 구하는 알고리즘

a,b(a>b)에 대해 a를 b로 나눈 나머지를 r이라 할 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 

b를 r로 나눠 나머지가 0이 나올때까지 구하고, 0이 나올때 나누는 수가 a와 b의 최대공약수이다.

 

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

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

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

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

 ----------------------------------

math모듈에 있는 최대공약수와 최소공배수 구하기

import math

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

 

 

www.acmicpc.net/problem/2609