알고리즘 - 최대공약수, 최소공배수

이동근·2021년 4월 17일
0

알고리즘

목록 보기
13/19

python으로 최대공약수 최소공배수 구하기

최대공약수

최대공약수는 2 숫자간의 공통된 약수 중 가장 큰 수를 말한다.

유클리드 호제법

호제법이라는 말은, 두 수가 상대방의 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 말한다.

최대공약수는
a와 b라는 수가 있을때
while b:
    a, b = b, a % b
return a 

이런식으로 구한다.

a = 3 , b = 12 일 경우 최대공약수는 '3' 이다.
a = 2 , b = 5 일 경우 최대공약수는 '1' 이다.

이걸 위의 유클리드 호제법을 사용해서 구하게 되면

이런식으로 쉽게 구할 수 있다.

최소공배수

최소공배수는 두 수의 배수 중 공배수에서 가장 작은 수를 구하면 됩니다.

만약

x = ab
y = bc 가 있으면

소인수분해를 했을때,
최대 공약수는 'b'가 됩니다.
최소 공배수는 abc가 됩니다.

그리고 여기서 x와 y를 곱하게 되면
xy = a b^2 c 가 되고
xy /b = abc가 되면서

최소공배수는 두 수를 곱한 값을 최대공약수로 나눈값이 됩니다.

위에 했었던 값들 중
3과 12의 최소 공배수는 12
2와 5의 최소공배수는 10이 됩니다.

이런식으로 최소공배수와 최대공약수를 쉽게 구할 수 있다.

profile
하루하루 1cm 자라는 개발자

0개의 댓글