最小公倍数と最大公約数

皆さんこんにちは
お元気ですか。私は元気です。

さて、今日は数学でも割りと使われる最小公倍数と最大公約数
のプログラムを組んでみました。

プログラムについて

説明

最小公倍数の求め方は２つのナンバーの最大公約数を求めて割ることだけです。
加えて、２つのナンバーを掛ければ解けます。

さて、最大公約数の解き方ですが、ユーグリッドの互除法と呼ばれるアルゴリズムを使います。

①大きい方から小さい方を引く
②引いた方から前の小さい方を引く
③数が等しくなるまで繰り返す。

訳がわからないので、実際に試してみます。
例えば12と8ならば・・・

１回目：12 - 8 = 4
２回目：8 - 4 = 4
4,4となったのでここで終了です。最大公約数は4です。

さて、実際のソースコードは以下の通りです。

ソースコード

#include <iostream>

using namespace std;

int ggd(int number1,int number2){
	int m = number1;
	int n = number2;

	if(number2 > number1){
		m = number2;
		n = number1;
	}

	while(m != n){
		int temp = n;
		n = m - n;
		m = temp;
	}

	return m;
}

int lcm(int number1,int number2){
	return number1 * number2 / ggd(number1,number2);	
}

int main(void){
	cout << ggd(12,8) << endl;
	cout << lcm(12,8) << endl;
}

結果

4
24