最大公倍数を求めるに当たって

Question

以下のソースコードでは入力された２つの正の整数に対して最大公約数と最小公倍数を出力します。このプログラムはきちんと動くのですが、最小公倍数を求めるbaisuu関数の、returnのところを、ab/yakusuu(a,b)として実行すると、コンパイルエラーはでないものの、明らかにおかしな数が出力されてしまいます。ab/yakusuu(a,b)でも式は間違っていないと思うのですがなぜ違うのでしょうか。
a*b/yakusuu(a,b)とすると
例えば
$ ./a.out
50000000 30000000
10000000 414
となってしまいました。
以下は正しいソースコードです。

#include <iostream>
#include <vector>
using namespace std;

unsigned int yakusuu(unsigned int a,unsigned int b){
	if((a==0)||(b==0)) return 0;
		while(a!=b){
		if(a>b)a=a-b;
		else b=b-a;
		}
	return a;
}
unsigned int baisuu(unsigned int a,unsigned int b){
	return (a/yakusuu(a,b))*b;
}
int main(){
unsigned int a,b;
vector<unsigned int> p,q;
int t=0;
while(cin>>a>>b){
p.push_back(a);
q.push_back(b);
t++;
};
for (int i = 0; i < t; i++)
{
	cout<<yakusuu(p[i],q[i])<<" "<<baisuu(p[i],q[i])<<endl;
}

}

Answer 1

50000000 * 30000000 が unsigned int の最大値よりも大きいためオーバーフローしているからだと思います。

#include <iostream>

int main()
{
    using namespace std;
    unsigned int a = 50000000, b = 30000000;
    cout << a * b << endl; // 4146708480
}

Comments

[ristori]

なるほど〜〜。納得しました。ありがとうございます。

Answer 2

ngyuki さんの回答にあるように、掛け算で オーバーフローがおきているのが原因ですね。

g++ をつかっているなら、
g++ -ftrapv ...
とすることで、整数のオーバーフローをランタイムに検出できるようになります。

参考：

• コンパイルや、ビルド時に付与したいオプション http://alpha-netzilla.blogspot.jp/2014/07/security.html

Comments

[ristori]

そのようなオプションがあったのですね。これはgccだけでなくg++でも使えるのでしょうか。$ g++ -g -ftrapv judge.cc -o ftrapv.exe としたのですが何も表示されません。

[katoy]

$ g++ 1.cpp
$ ./a.out
-148258816

これは オーバーフローを起こしているプログラムです。
つぎのようにすると、実行時にエラーがおきます。

$ g++ -ftrapv 1.cpp
$ ./a.out
Illegal instruction: 4