Ctrl+K

[問題] ユークリッドの互除法

[問題] ユークリッドの互除法#

「最大公約数を求める関数を実装しよう」

ユークリッドの互除法を使って、２つの数字の最大公約数を求める関数を作成しましょう！

ユークリッドの互除法

ユークリッドの互除法は，二つの自然数の最大公約数を求める方法で，「世界最古のアルゴリズム」として知られています．

【手順】

  1. 2つの自然数(a>b)のうち、大きい数aを小さい数bで割る

  2. 前の手順の除数bを前の手順の余りで割る

  3. これを余りが 0 となるまで繰り返す

  4. 余りが 0 のときの除数が最大公約数

def euclidean_algorithm(a, b):
    ...

# 正解チェック

print(euclidean_algorithm(28, 20) == 4)

False

実装例#

Hide code cell source 
def euclidean_algorithm(a, b):
    while a % b != 0:
        c = a % b
        a,b = b,c
    return b

    
euclidean_algorithm(28, 28)
Hide code cell output 
28

参考文献#

Web#

  1. ユークリッドの互除法 – 基礎数学演義３・第 2 回 (2024 年 4 月 16 日) | 和久井道久

  2. 高校数学の復習 ユークリッドの互除法 | 山形大学大学院理工学研究科廣瀬研究室

Contents