유클리드 호제법(최대공약수, 최소공배수 구하기)

유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘이다.

호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 냅니다.

a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 성질에 따라. b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수 입니다.

 

최대공약수

60과 24의 최대공약수를 구해보겠습니다.

 

gcd(60,24) -> gcd(24,12) -> 12

 

1. gcd(60,24)

 나머지 R : 60%24 = 12

 B: 24

 R: 12

 

2. gcd(B,R) -> gcd(24,12) 

 나머지 R : 24%12 = 0

 

->-> 12  

 

 

코드

public class 유클리드호제법 {
	public static void main(String[] args) {
		
        int num1=74;
        int num2=12;
        
        System.out.println(gcd(num1,num2));
	}
    
    private int gcd(int max, int min){
    	
        while(min!=0){
        	int remain=max%min;
            max=min;
            min=remain;
        }
        return max;
    }

}

 

만약 여러 숫자의 최대공약수를 구하고 싶다면 (A,B,C,D)

 

A와 B의 최대공약수를 A` 

A`과 C의 최대공약수를 A``

A``과 D의 최대공약수를 A```

 

최대공약수를 -> A``` 으로 구하시면 됩니다.

 

 

 

기존의 최대공약수를 구하는 알고리즘(1부터 작은수까지 모두 순회)은 O(min(a,b)) 이지만

유클리드 호제법을 사용해 최대공약수를 구하면 시간복잡도는 O(log2(min(a,b)))입니다.

 

 

최소공배수

(A,B)의 최소공배수 = (A*B)/(A,B)의 최대공약수 

즉, 위에서 최대공약수를 배우는 방법에 대해서는 설명되어 있으니 간단하게 구할 수 있습니다.

 

만약 여러 숫자의 최대공배수를 구하고 싶다면 (A,B,C,D)

 

A와 B의 최소공배수 A`

A`과 C의 최소공배수 A``

A``과 D의 최소공배수 A```

 

최소공배수 -> A```으로 구하시면 됩니다. 

 

만약 최소공배수 이용한 코드가 궁금하시다면

dkwjdi.tistory.com/120

[프로그래머스-lv2]N개의 최소공배수 -Java

 

이곳에 있습니다.

 

 

참고

dimenchoi.tistory.com/46