728x90
최대공약수 구할 때 사용하는 유클리드 호제법에 대해서 남기려고 한다.
최대공약수 GCD(Greatest Common Divisor)
최소공배수 LCM(Least Common Multiple)
두 수가 작은 수라면 소인수분해를 통해서 gcd와 lcm을 구할 수 있지만 숫자가 크다면 다른 방식으로 구해야한다.
유클리드 알고리즘이란 2개의 자연수(a,b)의 최대공약수를 구하는데
"자연수 a, b가 있을 때 (a>b, a!=b)
a를 b로 나눈 목을 q 나머지를 r이라고 했을 때 a = qb+ r이다.
GCD(a,b) = GCD(b,r)이며 r이 0일 때 b가 최대공약수이다."
만약 r=0이 아니면
a에는 b를 b에는 r을 넣어서 r=0이 나올 때까지 반복한다.
라는 원리이다.
그림으로 표현해보겠다.
mod연산에 대해서 알아야하는데
우리가 %연산자를 이용해서 나머지를 구하는 연산이다.
r이 0이 나올 때까지 큰 값에서 작은 값을 나눈 나머지를 계속 구하고
r이 0일 때의 작은 값이 최대공약수가 된다.
여기서 최소공배수도 구할 수 있는데 공식은
두 자연수 A,B의 최대공약수가 G이고 최소공배수가 L이면
A=a*G , B=b*G (a,b는 서로소)
L=a*b*G
A*B=L*G
서로소란, a,b가 서로소라는건 gcd(a,b)=1 <=> 공통인수가 없다.(1을 제외하고)
두 식이 성립한다.
LCM = GCD x (A/GCD) x (B/GCD) A,B는 a,b자연수의 초기값
이렇게 유클리드 호제법을 이용해서 최대공약수와 최소공배수를 쉽게 구할 수 있다.
코드로 구현하는 방법은 2가지가 있다.
1. 반복문을 이용
2. 재귀함수를 이용
반목문 이용
재귀함수 이용
반응형
댓글