유클리드 호제법
-
[Algorithm] - 유클리드 호제법 ( 최대 공약수 , 최소 공배수 )Algorithm/Algorithm 2022. 9. 15. 00:21
유클리드 호제법 ( 최대 공약수 ) 2개의 자연수에서 최대 공약수를 구하는 알고리즘 자연수 a , b 가 주어졌을 때 ( a>b 필수조건 ) r = a를 b로 나눈 나머지 값과 같다. a,b = b,r 가 반복되며, r이 0이 될 때 b의 값이 최소 공약수이다. 만약 여러 개의 수의 최대 공약수를 구하기 위해서는 a,b를 구하고 나온 값으로 계속 반복하여 구하면 구할 수 있다. a,b,c => gcd ( gcd(a,b) , c ) def GCD ( a , b ) : if b==0 : return a return GCD ( b , a%b ) print( GCD(78696,19332) ) LCM ( 최소 공배수 ) 최대 공약수를 활용하여 최소 공배수를 구하는 방식 a,b의 곱에서 최대 공약수로 나누면 값 된..