【Python入門】ユークリッドの互除法とはどんなアルゴリズムか？

概要

• 紀元前300年頃にギリシァで考案された
• ユークリッドの互除法は2つの整数 𝑎 と 𝑏 の最大公約数を求めるアルゴリズムである
• 人類最古のアルゴリズムだが、今現在でも最先端で使われている
• 最大公約数を求める上で最も効率の良いアルゴリズムである

どんなアルゴリズムか

1. 𝑥 に 𝑎 を代入する
2. 変数 𝑦 に 𝑏 を代入する./li>
3. 𝑦 ≠ 0 である間は 4 ～ 7を繰り返す
4. 𝑥 を 𝑦 で割ったときの商を 𝑞 とする
5. 𝑥 を 𝑦 で割ったときの余りを 𝑟 とする
6. 𝑥 に 𝑦 の値を代入する
7. 𝑦 に 𝑟 の値を代入する
8. 𝑛 に 𝑥 の値を代入する

Pythonで実装してみる

"2つの整数 a = 240, b = 144 の最大公約数をユークリッドの互除法で求める"

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from time import sleep


a = 240
b = 144

print("2つの整数 a = " + str(a) + ", b = " + str(b) + "の最大公約数をユークリッドの互除法で求める")

x = a
y = b

while y != 0:
    q = (x / y)
    r = (x % y)
    x = y
    y = r
    print("q=" + str(q) + ",r=" + str(r) + ",x=" + str(x) + ",y=" + str(y))
    sleep(1)
n = x

print ("最大公約数:" + str(n) )

結果：

2つの整数 a = 240, b = 144の最大公約数をユークリッドの互除法で求める
q=1,r=96,x=144,y=96
q=1,r=48,x=96,y=48
q=2,r=0,x=48,y=0
最大公約数:48