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

김가영·2020년 10월 5일
1

Algorithm

목록 보기
1/78
post-thumbnail

최대공약수를 구하면 최소공배수는 a * b / (최대공약수)

최대공약수를 구하는 가장 간단한 방법은 유클리드 호제법

유클리드 호제법

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

이를 이용하여 최소공배수와 최대공약수를 구하면

gcd = GCD(a,b)
lcm = a * b / gcd
profile
개발블로그

0개의 댓글