ユークリッドの互除法の実装【Rubyアルゴリズム】

環境

ruby 3.0.0

ユークリッドの互除法とは

• 提示された任意の2数a,bの最大公約数を求めるアルゴリズム
• 2つの数を比較し,大きい数から小さい数を引く…という処理を繰り返して、2つの数が等しくなったとき、その数はa,bの最大公約数になる
• 明示的に記述された最古のアルゴリズム
• 紀元前300年頃に記されたユークリッドの『原論』第 7 巻,命題 1 から3に記されている

アルゴリズム

• 任意の2数a,bを指定する
• a,bを比較する
• a,bのうち,大きい数から小さい数を引いた値を大きい数が格納された変数に代入する
  • a > b の場合,a = a-b
• 上記の比較を繰り返し、a = bになったとき、a(もしくはb)に格納された数値を最大公約数として出力する

コード

euclid.rb

#ユークリッドの互除法
def euclid(a,b)
  while a != b
    if a > b
      a = a - b
    else
      b = b - a
    end
  end
  return a
end

参考文献

アルゴリズムはじめの一歩完全攻略 / 矢沢久雄著. -- 東京 : 技術評論社 , 2019.2. -- 287p ; 23cm. -- (新・標準プログラマーズライブラリ). -- JavaとC言語のサンプルコードのダウンロードサービス付き. -- ISBN 9784297103941 ; (BB27793887) ; https://ci.nii.ac.jp/ncid/BB27793887
著者標目: 矢沢, 久雄. -- 分類: NDC8 : 007.64 ; NDC9 : 007.64 ; NDC10 : 007.64. -- 件名: BSH : プログラミング(コンピュータ) ; BSH : アルゴリズム