GCD関数

本ページには広告が含まれています。

引数に指定した配列の最大公約数(Greatestグレイテスト Commonコモン Divisorディバイザー)を求めます。ユークリッドの互除法で最大公約数を求めています。

構文
  1. Double = GCD( array )
引数
array 必須
最大公約数を求める数値を格納した配列
戻り値
最大公約数

プログラム

UWSC

解説

    2行目
    UWSC
    arrayの要素数を変数cに代入。
    3行目
    UWSC
    arrayのc-1番目をc-2番目で割った余りをremに代入。
    4,12行目
    UWSC
    remの値が0ならば5行目>>>を実行。
    5-11行目
    UWSC
    arrayの要素数が2ならば、arrayのc-2番目を返して終了。
    配列の要素数をc-2にする。GCDを再帰呼び出し。
    13-15行目
    UWSC

公約数と最大公約数について

公約数とは

2つ以上の自然数についていずれの約数にもなることができる整数のことを公約数といいます。言い換えると、共通している約数のことを指します。例えば、8と12の公約数は、まず8の約数が1、2、4、8で、12の約数が1、2、3、4、6、12なので、共通している1、2、4となります。

最大公約数とは

最大公約数とは、共通する約数(公約数)のうち最大の整数のことです。8と12の最大公約数は約数のうちで最大の整数である4となります。

ユークリッドの互除法

ユークリッドの互除法とは2つの自然数の最大公約数を求める方法で、以下の性質を使って最大公約数を求めます。

POINT
2つの自然数\(a\),\(b\)(\(a \ge b\))について、\(a\)を\(b\)で割ったときの商を\(q\)、余りを\(r\)とすると「\(a\)と\(b\)の最大公約数」は、「\(b\)と\(r\)の最大公約数」に等しい。

これらの性質を利用したユークリッドの互除法での手順は以下のようになります。

手順
  1. \(a\)を\(b\)で割り、余り\(r\)を求める。
  2. \(b\)を手順1の余り\(r\)で割り、その余り\(r_{1}\)を求める。
  3. \(r\)を手順2の余り\(r_{1}\)で割り、その余り\(r_{2}\)を求める。
  4. \(r_{1}\)を手順3の余り\(r_{2}\)で割り、その余り\(r_{3}\)を求める。
  5. 以降、\(r_{n}\)を\(r_{n+1}\)で割り、その余り\(r_{n+2}\)を余りが0になるまで繰り返し求めていく。
余りが0になったときの割る数の値が最大公約数となります。

これを式で表すと以下のようになります。

\begin{eqnarray} a \; &\div& \; \color{blue}{b} \; &=& \; q \; &\mod& \; \color{red}{r} \\ \color{blue}{b} \; &\div& \; \color{red}{r} \; &=& \; q_{1} \; &\mod& \; \color{green}{r_{1}} \\ \color{red}{r} \; &\div& \; \color{green}{r_{1}} \; &=& \; q_{2} \; &\mod& \; \color{pink}{r_{2}} \\ \color{green}{r_{1}} \; &\div& \; \color{pink}{r_{2}} \; &=& \; q_{3} \; &\mod& \; r_{3} \\ \end{eqnarray}

以下は1071と1029の最大公約数を求める例です。

\[ \begin{eqnarray} 1071 \; &\div& \; \color{blue}{1029} \; &=& \; 1 \; &\mod& \; \color{red}{42} \\ \color{blue}{1029} \; &\div& \; \color{red}{42} \; &=& \; 24 \; &\mod& \; \color{green}{21} \\ \color{red}{42} \; &\div& \; \color{green}{21} \; &=& \; 2 \; &\mod& \; 0 \end{eqnarray} \]

余りが0になったときの割る数である21が最大公約数です。

プログラム実行例

最大公約数を求めます

12と18の最大公約数を求めます。

  • Main
  • FUNCTIONS
UWSC
UWSC
結果
プレーンテキスト
使用関数

二次方程式を解く

  • Main
  • FUNCTIONS
UWSC
UWSC
結果
プレーンテキスト
使用関数

関連記事

factDouble関数 (自作関数)
引数に指定した数値の二重階乗を求めます。
fact関数 (自作関数)
引数に指定した数値の階乗を求めます。
roundOff関数 (自作関数)
指定した位置で四捨五入します。
Collatz関数 (自作関数)
コラッツ数列を求め結果を配列で返します。
primeFactorization関数 (自作関数)
数値を素因数分解した値を格納した配列を返します。
digitSum関数 (自作関数)
数値の各桁の和を返す
divisors関数 (自作関数)
引数に指定した数値の約数のリストを返します。
normalizeAngle関数 (自作関数)
度単位の角度を0~360度に正規化します。
ROMAN関数 (自作関数)
アラビア数字をローマ数字に変換します。
ARABIC関数 (自作関数)
ローマ数字をアラビア数字に変換します。