3つ以上の整数の最小公倍数を求める

投稿日: 2009/2/8 日曜日作成者: コスミー

2つの数の最大公約数を求める→2つの数の最小公倍数を求める。
求めた最小公倍数と次の数の最小公倍数を同じ手順で求める。
繰り返す。

こんな感じ？

・ユークリッドの互除法で2つの数の最大公約数を求める関数


int gcm(int a, int b) {
	int result = a;
	int k = 0;
	int n = b;
	do {
		k = result % n;
		result = n;
		n = k;
	} while(k != 0);
	return result;
}

・最大公約数を利用して2つの数の最小公倍数を求める関数


int lcm(int a, int b) {
	int g;
	g = gcm(a, b);
	return a*b/g;
}

・2つの数の最小公倍数を順次求めて3つ以上の数の最小公倍数を求める関数


int lcm_n(vector<int> &numbers) {
	int l;
	l = numbers[0];
	for (int i = 1; i < numbers.size(); i++) {
		l = lcm(l, numbers[i]);
	}
	return l;
}

悔しいからここに書く。

以上

コスミーについて

昔（？）はゲーム作ってました。今もなんか作ろうとしています。