최대 공약수, 최소 공배수

최대 공약수(GCD : Greatest Common Divisor)

두 수의 공약수중 가장 큰 수

 

첫번째 방법.

2부터 둘 중 작은 수까지 계속 나눠 보는 방법

 

두번째 방법.

유클리드 호제법 : gcd(a,b) = gcd(b, a%b)  임을 이용.

 

 

최소 공배수(LCM : Least Common Multiple)

두수의 공배수중 제일 작은 수

 

최대 공약수를 이용해 구하는 방법.

lcm(a,b) = ab/g   ( g =  gcm(a,b) )

 

오버플로우를 조심.

 

a/g * b/g *g 같은 방식으로 구하면 조금 덜 수 있다.