キンサクプログラマー

お金儲けと技術のメモ

毎日アルゴリズム(第2日目)ユークリッドの互除法

ユークリッドの互除法

他のアルゴリズムをやろうとしたが間に合わず急遽変更。
高校生レベルのユークリッドの互除法で満足しとく。

概要

二つの数字の最大公約数を高速に求めるアルゴリズム
通常であれば素因数分解などで求めるが、こちらの方が早いらしい。

アルゴリズム

  • 二つの数字をa,bとおく
  • a,bの最大公約数をGとする
  • a=An,b=Bnとなる
  • a=bx+qとも表せる
  • 上の式を代入するとAn=Bnx+q
  • 移行してゴニョるとq=n(A-Bx)
  • なんと、aをbで割った時のあまりqも実は最大公約nで割れる

これだけ

ソース

github.com