유클리드 호제법(최대공약수)

유클리드 호제법이란?

두 수의 최대공약수를 구하는 알고리즘

 

 

원래 최대공약수를 구하려면 소인수분해를 해야하는데

유클리드 호제법을 사용하면 더 간단하게 구할 수 있다.

ex) 

24 = 2 x 2 x 2 x 3

36 = 2 x 2 x 3 x 3

최대공약수는 2 x 2 x 3 = 12!

 

유클리드 호제법은 나머지연산(%)를 계속하는 것.

36 % 24 = 12

24 % 12 = 0

12가 36, 24의 최대공약수!!!!!!!

 

유클리드 호제법 사용해서 최대공약수 구하는 알고리즘

	while(n != 0){
            int tmp1 = m % n; //큰 수를 작은 수로 나누기
            m = n; //작은 수가 큰 수가 되고 나머지로 나눠야 하니까 m에 n 넣어주기
            n = tmp1; //n으로 나눠야하니까 나머지를 n에 넣어주기
        }