A社の佐伯さんがのらりくらりと

A社の佐伯さんがのらりくらりと。インターネットと少しだけ生活のこと。

【アルゴリズムの勉強】Pythonでユークリッドの互除法を書いてみた

学習エントリ。

Pythonユークリッドの互除法を実装する。

ユークリッドの互除法ってなんぞ

ユークリッドの互除法ユークリッドのごじょほう、英: Euclidean Algorithm)は、2 つの自然数の最大公約数を求める手法の一つである。
2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。
明示的に記述された最古のアルゴリズムとしても知られ、紀元前300年頃に記されたユークリッドの『原論』第 7 巻、命題 1 から 3 がそれである

ユークリッドの互除法 - Wikipedia

# coding: utf-8

x = 108
y = 648

def gcd(x,y): 
	while y != 0:
		x , y = y , x % y 
	return x

print(gcd(x,y)) ##108