ryubloblog’s diary

宮城県の仙台で働くプログラマーです。

最大公約数を求めるプログラムを様々な方法で解く【PHP】【Python】

現在進行中でアルゴリズムの学習をしていて、最大公約数を求めるプログラムを書く際に、
様々なコードの書き方を学んだので記事にしたいと思います。
下記の形で入力されます。

A B

A Bの条件としてA < Bとしています。(条件分岐を付け加えれば良い話なのですが、、)

方法1:共通に割れる数を1から求める方法

この方法は2つの数を1から順に割っていき、割り切れた最大値を求めるプログラムになります。

下記、PHPでの実装例になります。

<?php

[$a, $b] = explode(' ', trim(fgets(STDIN)));

function gcd($a, $b)
{
  $answer = 0;
  for ($i = 1; $i <= min($a, $b); $i++) {
    if ($a % $i === 0 && $b % $i === 0) $answer = $i;
  }
  return $answer;
}

echo gcd($a, $b);

この方法では、余りの計算を行う際に2×min($a, $b)回行うことになるので、効率的な方法ではないと言えます。

方法2:ユークリッドの互除法を使用する

この方法はユークリッドの互除法というアルゴリズムを用いて、最大公約数を求めます。

ユークリッドの互除法の処理手順は
1. A,Bの大きい方の数を「大きい方の数を小さい方の数で割った余り」に置き換える
2. 1を繰り返し、どちらかが0になったら処理を止める
3. 0ではない方の数が最大公約数の値

下記、PHPPythonでの実装例になります。

<?php

[$a, $b] = explode(' ', trim(fgets(STDIN)));

function gcd($a, $b)
{
  while ($a >= 1 && $b >= 1) {
    if ($a < $b) {
      $b = $b % $a;
    } else {
      $a = $a % $b;
    }
  }
  if ($a >= 1) return $a;
  return $b;
}

echo gcd($a, $b);

a, b = map(int, input().split())

def gcd(a, b):
  while a >= 1 and b >= 1:
    if a < b:
      b = b % a
    else:
      a = a % b
  if a >= 1:
    return a
  return b

print(gcd(a, b))

この方法の場合、最大公約数を求める時の計算量はO(log(A+B))となるらしいので、
方法1に比べかなり効率的になりました。
※ 計算量については勉強中なので、詳しくはのちのブログでまとめたいと思います。

方法3:再帰関数を使用する

この方法は方法2の処理を簡潔に記述することができるものになるので、新しい方法ではなく、
コードの記述量を減らすことができるテクニックのようなものになります。

下記、PHPPythonでの実装例になります。

<?php

[$a, $b] = explode(' ', trim(fgets(STDIN)));

function gcd($a, $b)
{
  if ($b === 0) return $a;
  return gcd($b, $a % $b);
}

echo gcd($a, $b);
a, b = map(int, input().split())

def gcd(a, b):
  if b == 0:
    return a
  return gcd(b, a % b)

print(gcd(a, b))

再帰関数を使用することによってコードの記述量を大幅に減らすことができました。
ただ、再帰関数は処理イメージを掴みにくい点があるので、
再帰関数の処理イメージについては別で詳しくまとめれたらと思います。

最後に

今回が初の投稿となるのですが、ここまで読んでいただきありがとうございました。
まだまだ、不慣れな部分はありますがよろしくお願いいたします。