[수학1]최대공약수

Greatest Common Divisor

• 최대 공약수를 줄여서 GCD 라고 쓴다.
• 두 수 A 와 B 이 최대공약수 G는 A 와 B 의 공통된 약수 중에서 가장 큰 정수이다.
• 최대공약수를 구하는 가장 쉬운 방법은 2 부터 min(A,B)까지 모든 정수로 나누어 보는 방법
• 최대공약수가 1인 두 수를 서로소(Comprime)라고 한다.

방법 1 . 작은 수 부터 차례로 계산해보기

int g =1;
for (int i=2; i<min(a,b); i++) {
	if (a % i == 0 && b % i == 0) {
    	g = i;
    }
}

방법 2. 두 수를 비교후 작은 수를 구한 후 그 수부터 하나씩 빼면서 나눠보기

  public int GCD(int a, int b){
        int small = 0;
        if (a > b) {
            small = b;
        }else {
            small = a;
        }
        for (int i=small; i > 0; i--) {
            if ((a % i == 0) && (b % i == 0) ){
                return i;
            }
        }
        return -1;
    }

방법 3. 유클리드 호제법

• 위의 두 방법보다 빠른 방법이다
• a 를 b 로 나눈 나머지를 r 이라고 했을 때 GCD( a , b) = GCD (b, r) 과 같다.
• r이 0 이면 그 때 b 가 최대 공약수이다
• GCD(24,16) = GCD(16,8)= GCD(8,0)=8

재귀함수를 사용해서 구현한 유클리드 호제법
    public static int GCD(int a, int b){
        if (b == 0){
            return a;
        }else {
            return GCD( b, a%b);
        }
    }

아래와 같이 두수를 바꿀 필요가 없음

if (n1 > n2){
    sb.append(GCD(n1,n2)).append("\n");
}else {
    sb.append(GCD(n2,n1)).append("\n");
}

ex ) GCD(16 ,24) =GCD(24 ,16) 이 되기 때문이다

 

방법 4. 재귀함수를 사용하지않고 구현한 유클리드 호제법

public static int GCD(int a, int b){
    while(b != 0){
        int r = a %b;
        a = b;
        b = r;
    }
    return a;
}