최대공약수

수론에서, 정수들의 공약수(公約數, 영어: common divisor)는 동시에 그들 모두의 약수인 정수다. 적어도 하나가 0이 아닌 정수들의 최대공약수(最大公約數, 문화어: 련속나눔셈; 영어: greatest common divisor, 약자 GCD)는 공약수 가운데 가장 큰 하나다. 다항식이나 환의 원소에 대해서도 정의할 수 있다.

재귀방식 (logN)

int GCD(int a, int b) {
 
	if (b == 0) { return a; }
	else { return GCD(b, a%b); }
}

반복문 방식 (logN)

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