これからは、整数論関係のプログラム(関数)をのせることにするね。

最初の関数は、最大公約数を求めてくれるもの。ユークリッド互除法ともいう。

2つ以上の自然数に共通する約数(公約数)のうち、最大のものを最大公約数という。 ちなみに、いくつもの自然数に共通する倍数(公倍数)のうち最小のものを最小公倍数という。

最小公約数は 1、最大公倍数は無限大なので、最小公約数や最大公倍数を考えることはふつうはない。

<関数名>
  gcd ---- 最大公約数を算出する

<形式>
  int gcd(int n1, int n2);

<引数>
  n1、n2 2つの自然数

<関数値>
  2つの自然数の最大公約数

用例
  gcd(1996, 2000);

<関数本体>
  gcd.c

<説明>
  最大公約数を求める方法は、2千年以前の古代ギリシャ人により発見され、ユークリッドの著書「Elements」に詳しく書かれており、ユークリッドのアルゴリズムといわれている。
  Lameの定理により、このアルゴリズムは小さい方の自然数の桁数の5倍以内で必ず終了するが判り、計算量は O(logN) になる。
 また、n個数の最大公約数を求めるには、まず最初の2つについてここの方法を適用して最大公約数を求め、つぎに3つ目の数と計算した最大公約数から再び最大公約数を計算する。このように最後の数まで繰] り返せば、n個の自然数の最大公約数が求められる。

Comments are closed.

Post Navigation