euclid.c

ユークリッドの互除法を用いて，２数の最大公約数および最小公倍数を求める [詳細]

#include <stdio.h>
#include "sub.h"

euclid.cのインクルード依存関係図

ソースコードを見る。

関数
	main (int argc, char **argv)
	２数の最大公約数,および，最小公倍数を求める

---

説明

ユークリッドの互除法を用いて，２数の最大公約数および最小公倍数を求める

作者:

工芸太郎

日付:

2008/04/01 Ver. 1

euclid.c で定義されています。

---

関数

main	(	int	argc,
		char **	argv
	)

２数の最大公約数,および，最小公倍数を求める

ユーグリッドの互除法を用いて最大公約数，最小公倍数を求める

• 使用方法: euclid n m
• 最大公約数の性質
  • ２数を n, m (n>=m)とし，その最大公約数を gcm(n,m) と表す．
    このとき，gcm(n,m) = gcm(m,n%m) が成立する．
    ただし，n%m は nをmで割った余りを意味する．
• ユークリッドの互除法
  • n を m で割った余り r1 を求める (m > r1 >= 0)
  • m を r1 で割った余り r2 を求める (r1 > r2 >= 0)
  • r1 を r2 出割った余り r3 を求める (r2 > r3 >= 0)
  • ...
    n > m > r1 > r2 > ... >= 0 であり,いつか余りは0となる．
    r(k-1) % r(k) = 0
    となったとき，r(k) が n, m の最大公約数である

• アルゴリズム
  1. m=0 の場合，nが求める値である
  2. m!=0 の場合，m, n%m の最大公約数を求める

引数が与えられた場合は，引数を使用する

引数が省略された場合は，キーボード(標準入力)から値を読み込む

euclid.c の 35 行で定義されています。

参照先 gcm()・lcm().

---