最大公約数

最大公約数(GCD)を求める関数を作成する。 以下では、便宜上 GCD(0,0)=0 とする。

コード例1

ユークリッドの互除法を用いる。

#include <stdio.h>
int GCD(int, int);
int main()
{
	int a = 12;
	int b = 18;
	printf("GCD(%d,%d)=%d\n", a, b, GCD(a, b));
}
int GCD(int a, int b) {
	if (a < 0) { a *= -1; }
	if (b < 0) { b *= -1; }
	while (b != 0) {
		int tmp = a;
		a = b;
		b = tmp % b;
	}
	return a;
}

実行結果. 6

コード例2

ユークリッドの互除法を利用する点は同じだが、再帰的に計算する方法。

#include <stdio.h>
int GCD(int, int);
int main()
{
	int a = 12;
	int b = 18;
	printf("GCD(%d,%d)=%d\n", a, b, GCD(a, b));
}
int GCD(int a, int b) {
	if (b == 0) {
		return a > 0 ? a : -a;
	}
	return GCD(b, a % b);
}

実行結果. 6

実行速度

いくつか実験した結果、コード例1に比べてコード例2で作成したものは1.8~1.9倍程度遅かった。