オリジナルの数学ライブラリ

プログラミングの練習として簡単な計算を行うライブラリを作成しましょう

最大公約数を求める関数GCD()

最大公約数はすべての公約数を約数にもつ公約数の事です。 例えば12と18の場合、最大公約数は6となります。 これを実装するとGCD(12,18)=6となるようにプログラムを作成する必要があります

$$GCD(12,18)=6$$

数字を１から試すのもありですが、「ユークリッドの互除法」というアルゴリズムがあります ユークリッドの互除法では、割られる数と２つの数字の剰余を割った時の余った数を使用して最大公約数を出します。12と18を例に挙げると以下のような挙動をします

18/12=1..6 12/6=2..0

2回目の計算時に余りが0になりました。その時の割った数字(=6)が最大公約数であることが分かります

実装

F#には再帰関数がサポートされているためこれを活用していきます もし最大公約数が1の場合はそのまま1を返すようにします

let rec GCD(x,y)=
    match y with
        |1->1
        |0->x
        |_->GCD(y,x%y)