引数に指定した配列の最大公約数（Greatest Common Divisor）を求めます。ユークリッドの互除法で最大公約数を求めています。
- 構文
- Double = GCD( array )
- 引数
- array 必須
- 最大公約数を求める数値を格納した配列
- 戻り値
- 最大公約数
プログラム
解説
- 2行目
- arrayの要素数を変数cに代入。
- 3行目
- arrayのc-1番目をc-2番目で割った余りをremに代入。
- 4,12行目
- remの値が0ならば5行目>>>を実行。
- 5-11行目
- arrayの要素数が2ならば、arrayのc-2番目を返して終了。
配列の要素数をc-2にする。GCDを再帰呼び出し。 - 13-15行目
公約数と最大公約数について
公約数とは
2つ以上の自然数についていずれの約数にもなることができる整数のことを公約数といいます。言い換えると、共通している約数のことを指します。例えば、8と12の公約数は、まず8の約数が1、2、4、8で、12の約数が1、2、3、4、6、12なので、共通している1、2、4となります。
最大公約数とは
最大公約数とは、共通する約数（公約数）のうち最大の整数のことです。8と12の最大公約数は約数のうちで最大の整数である4となります。
ユークリッドの互除法
ユークリッドの互除法とは2つの自然数の最大公約数を求める方法で、以下の性質を使って最大公約数を求めます。
これらの性質を利用したユークリッドの互除法での手順は以下のようになります。
- \(a\)を\(b\)で割り、余り\(r\)を求める。
- \(b\)を手順1の余り\(r\)で割り、その余り\(r_{1}\)を求める。
- \(r\)を手順2の余り\(r_{1}\)で割り、その余り\(r_{2}\)を求める。
- \(r_{1}\)を手順3の余り\(r_{2}\)で割り、その余り\(r_{3}\)を求める。
- 以降、\(r_{n}\)を\(r_{n+1}\)で割り、その余り\(r_{n+2}\)を余りが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の最大公約数を求めます。
二次方程式を解く
関連記事
- fact関数 (自作関数)
- 引数に指定した数値の階乗を求めます。
- factDouble関数 (自作関数)
- 引数に指定した数値の二重階乗を求めます。
- ABS関数 (スクリプト関数)
- 引数の絶対値（\(|x|\)）を返します。
- ARCCOS関数 (スクリプト関数)
- 引数の逆余弦を求めます。
- CEIL関数 (スクリプト関数)
- 正の値へ切り上げた数値を返します。
- LN関数 (スクリプト関数)
- 自然対数（\(\log_e{x}\)）を求める。
- LOGN関数 (スクリプト関数)
- Baseを底とするXの対数（\(\log_{Base}{x}\)）を求める。
- ZCUT関数 (スクリプト関数)
- マイナス値は0にして返します。
- ARCSIN関数 (スクリプト関数)
- 引数の逆正弦を求めます。
- EXP関数 (スクリプト関数)
- 自然指数関数（\(y=e^{x}\)）を求める。