[Java] 유클리드 호제법 - 최대공약수, 최소공배수

최대공약수, 최소공배수 구하기 알고리즘

 

 

유클리드 호제법 알고리즘

 

 

 1. 반복문 돌리기

int a = 12, b = 3;
int gcd = 0 , lcm = 0;
int r = 1;


//최대공약수 구하는 메소드
int gcd( int a , int b ){
	while( r > 0 ){
		r =  a % b;
    		a = b;
    		b = r;
   	}
   return a;
}


gcd = gcd(a , b);
lcm = (a * b) / gcd;
    

 

 

 

 2. 재귀 함수 사용

int a = 12, b = 3;
int gcd = 0, lcm = 0;

//반복문처럼 도는 재귀함수.
int makeGCD( int a, int b){
	if( b == 0){
    	return a;
    } else {
    	return gcd( b, a%b );
    }
}

gcd = makeGCD(a , b);
lcm = ( a * b ) / gcd;