スマートフォン用の表示で見る

ユークリッドの互除法

サイエンス

ユークリッドの互除法

ゆーくりっどのごじょほう

最大公約数を求めるときに使うアルゴリズムとして有名。

算法を簡単に示すと、たとえば 1981 と 777 の最小公倍数を求める場合

1981 を 777 で割った余りは 427、
777 を 427 で割った余りは 350、
427 を 350 で割った余りは 77、
350 を 77 で割った余りは 14、
77 を 14 で割った余りは 7、
14 は 7 で割り切れる。
よって 1981 と 777 の最大公約数は 7 である。

Java によるアルゴリズムで書くと a, b の最小公倍数 gcm は (a, b整数型でそれぞれ自然数が与えられているものとする)

long gcm, c;

do {
 c = a % b;
 a = b; b = c;
} while (c != 0);

gcm = a;

*リスト:リスト::数学関連