최대공약수 & 최소공배수

예) 21, 72 의 최대공약수 & 최소공배수 구하기

 

① 최대공약수

    72 % 21 = 9

    21 % 9 = 3

    9 % 3 = 0

    ∴ 최대공약수 = 3

 

② 최소공배수

    (21 * 72) / 최대공약수

    = (21*72)/3 = 504

    ∴ 최소공배수 = 504

 

 

 

 

 

코드구현

public static void main(String[] args){
	int x = 21;
    int y = 72;
    
    int gcd = makegcd(x,y);
    System.out.println("최대공약수 : " + gcd);
    
    int lcd = (x*y) / gcd;
    System.out.println("최소공배수 : " + lcd);
}
    
private int makegcd(int x, int y){
	while(x>0){
    	int temp = y%x;
        y = x;
        x = temp;
	}
    
    return y;
}