fc2ブログ



最大公約数

2006.04.26 23:21  整数

2つの正の整数 x と y の最大公約数とは

x / d と y / d の余りがともに 0 となる d のうち最大のもの

を言います。最大公約数は英語で Greatest Common Divisor と言われ、一般的に gcd と略されます。いくつか例を見てみましょう。

gcd(35, 14) = 7
(公約数 1, 7 のうち最大の数である 7)
gcd(128, 192) = 64
(公約数 1, 2, 4, 8, 16, 32, 64 のうち最大の数である 64)


誰もが思いつく最大公約数を求める方法が、以下の力任せのアルゴリズムです。

001 int gcd( int x, int y ){
002     int n;
003     n = min( x, y ); // x と y の小さい方
004     // n から 1 までの数で、x と y を順に割っていき、
005     // 余りが 0 になったらその数を返す
006     for ( int d = n; d >= 1; d-- ){
007         if ( x % d == 0 && y % d == 0 ) return d;
008     }
009     assert ( false ); // 入力に 0 がきたらエラー
010 }


このアルゴリズムは実用的ではありません。
スポンサーサイト



| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ