최대공약수와 최소공배수 구하기

최대공약수(Great Common Divisor / GCD)
어느 수들의 공통된 약수중 가장 큰 약수를 최대 공약수라고 한다.

<유클리드 호제법>

int a, b;
int r=a%b;
int g; //g는 최대공약수
gcd(a,b)=gcd(b,r);
if(r==0){
	g=b;
}


////재귀함수를 사용한 유클리드 호제법 구현
int gcd(int x, int y){
    if(b==0){
         return a;
         }else{
               return gcd(b, a%b);
         }
    }
    
////재귀함수를 사용하지 않는 유클리드 호제법 구현
int gcd(int a, int b) {
		while(b!=0) {
			int r=a%b;
			a=b;
			b=r;
		}
		return a;
		
	}

최소 공배수(Least Common Multiple/LCM)
어느 수들의 공통된 배수 중 가장 작은 배수를 최대 공배수라고한다.

public static int lcm(int a, int b) {
		int l = a*b/gcd(a,b);
		return l;
	}