最大公約数

最大公約数は、ユークリッド互除法で求める

ユーリッド互除法の定理

整数XとY(X≧Y)を与えたとき、XをYで割った時の余り(剰余)をRとすると、XとYの最大公約数は、YとRの最大公約数と等しい。

ただし。Xと0との最大公約数はXとする。

 

整数XとY(X≧Y)の最大公約数を変数GCDに求める

手順

  1. 変数RにX÷Yの剰余(余り)を代入
  2. 変数Rが0でない間、以下の手順3~5を繰り返す
  3. 変数Xに変数Yの値を代入する
  4. 変数Yに変数Rの値を代入する
  5. 変数RにX÷Yの剰余(余り)を代入する
  6. 変数GCDに変数Yの値を代入する

 

 

コメントを残す

メールアドレスが公開されることはありません。