최대공약수 (Greatest Common Divisor)

참고

https://ko.wikipedia.org/wiki/%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98

최대공약수 - 위키백과, 우리 모두의 백과사전

정의

• 두 수 A, B의 공통된 약수 중에서 가장 큰 정수

• 최대공약수가 1인 두 수를 서로소(Copreme)라고 한다.

최대공약수를 구하는 방법

1) 2부터 A, B중 작은 수까지 모든 정수로 나누어 보는 방법

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

2) 유클리드 호제법(Euclideanalgorithm)을 이용하는방법

• A를 B로 나누어 나머지 R을 구한 뒤, B를 R로 나눈다.

• 나머지가 0이 될때까지 반복한다.

public static int gcd(int a, int b) {
	if(b == 0) {
		return a;
	} else {
		return gcd(b, a%b);
	}
}

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