Home > C++ | 聞いて欲しい独り言 > 3つ以上の整数の最小公倍数を求める

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

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;
}

悔しいからここに書く。

以上

Comments:3

o-taki 09-02-12 (木) 18:24

for ( res=1; true; res++){
count=0;
for ( i=0; i=3 ) break;
}
return res;

o-taki 09-02-12 (木) 18:28

盛大にエスケープされた。

for ( res=1; true; res++){
count=0;
for ( i=0; i<numbers.length; i++ ){
if ( res%numbers[i]==0 ) count++;
if ( count>=3 ) break;
}}
return res;

コスミー 09-02-13 (金) 2:12

テストするぜ。

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;
}

Comment Form
Remember personal info

Trackbacks:0

Trackback URL for this entry
http://red-treasure.com/report/wp-trackback.php?p=333
Listed below are links to weblogs that reference
3つ以上の整数の最小公倍数を求める from コスミー報告書[社外秘]

Home > C++ | 聞いて欲しい独り言 > 3つ以上の整数の最小公倍数を求める

Search
Feeds
Meta
 合計:008045
 今日:0044 昨日:0112

Return to page top