[알고리즘] 유클리드 호제법

유클리드 호제법(eucildean algorithm)

2개 수의 최대공약수를 구하기 위해 사용하는 알고리즘

2개의 수 중 더 작은 수로 큰 수를 나눈 나머지를 구하고,

작은 수와 나머지 숫자를 각각 큰 수 / 작은 수로 다시 정의하여 나머지가 0이 되면 해당 수를 최대공약수로 결정하는 방법

이때 마지막에 0으로 나눈 작은수가 최대공약수가된다.

 

자바로 구현해보자

package theory;

import test.sout;

public class euclide {
	
	public static void main(String[] args) {
		
		int numa = 615146;
		int numb = 310232;
				
		euclide(numa,numb);
		
		System.out.println(numb/4);
		System.out.println(numa/4);
	}

	private static void euclide(int bigNum, int smallNum) {
		
		int remain=0;
		remain = bigNum>smallNum ? bigNum%smallNum : smallNum%bigNum; 
		
		if(remain>0) {
			euclide(smallNum,remain);
		}else {
			System.out.println("최대공약수는 "+smallNum);
			System.out.println("remain"+remain);
			System.out.println("bignum"+bigNum);
			
			
		}
	}

}