튜기's bloggggg(st1tch)

나머지공식을 이용해서 a와 b의 최대공약수를 구하는 코드

알고리즘 풀때 한번씩 사용하는 함수



두 정수 a, b의 최대공약수를 g, 최소공배수를 이라고 하면 다음이 성립한다.

(1) a = ga′, b = gb′ (단, a′, b′는 서로소)
(2) l = gab
(3) lg = ab
(4) a = ga′, b = gb′ 일 때 a ± b′ = g(a′ ± b′)
(5) 두 정수 a, b의 모든 공약수는 g의 약수이다.
(6) 두 정수 a, b의 모든 공배수는 l의 배수이다.


위 성질을 이용해서 최소공배수도 쉽게 구할 수 있다.



[출처] 최대공약수 구하기|작성자 튜기


저작자 표시
신고

Comment +0