Help us understand the problem. What is going on with this article?

ユークリッドの互除法による最大公約数の求め方

概要

ユークリッドの互除法とは、2つの自然数の最大公約数(Gratest Common Divisor)を求める手法の一つです。一方をもう一方で割って剰余を求め、その剰余を使ってさらに除算を繰り返すことで、最終的に剰余が0になった時点で最大公約数を見つけることができます。最古のアルゴリズムとしても知られ、紀元前300年頃に編纂されたユークリッドの『原論』にその記述があります。

Euclidean_algorithm_252_105_animation_flipped.gif

実装例

def gcd(a, b):
    # 大きい方を被除数、小さい方を除数とする
    dividend = max(a, b)
    divider = min(a, b)

    if divider == 0:
        return dividend

    # 最大公約数を見つけるまで繰り返す
    while dividend % divider != 0:
        # 除算を行い、その除数を次回の被除数、剰余を次回の除数として処理を繰り返す
        r = dividend % divider
        dividend = divider
        divider = r

    # 一方がもう一方を割り切れた時点で、その除数を最大公約数とみなせる
    return divider

注意点

厳密には被除数と除数の大小関係は関係ない(被除数の方が小さい場合、被除数がそのまま剰余となり、次回の処理で除数と入れ替わる)のですが、本記事では直感的にわかりやすくするため最初の除算で大きい方を小さい方で割るようにしています。

参考

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_B
https://ja.wikipedia.org/wiki/ユークリッドの互除法

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away