最大公約数
2006.04.26 23:21 整数
2つの正の整数 x と y の最大公約数とは
x / d と y / d の余りがともに 0 となる d のうち最大のもの
を言います。最大公約数は英語で Greatest Common Divisor と言われ、一般的に gcd と略されます。いくつか例を見てみましょう。
誰もが思いつく最大公約数を求める方法が、以下の力任せのアルゴリズムです。
このアルゴリズムは実用的ではありません。
を言います。最大公約数は英語で 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) | ↑ページトップ |