Python の最大公約数 (HCF / GCD)
ユークリッド アルゴリズムを使用して、2 つの数値の最大公約数 (HCF) または最大公約数 (GCD) を計算します。
概要
最大公約数 (GCD) とも呼ばれる最大公約数 (HCF) は、2 つ以上の整数を余りを残さずに除算する最大の正の整数です。
ユークリッド アルゴリズムは、HCF を計算するための非常に効率的な方法です。 2 つの数値の GCD もその差を除算すると述べています。
Python では、while ループを使用してこれを反復的に実装し、より大きな数値を除算の余りで継続的に置き換えます。
コードと実行の出力
2 つの数の HCF/GCD を求めるユークリッド ループの実装。
hcf_gcd.py
エディターで試してみるdef find_gcd(a, b):
# Euclidean Algorithm
while b != 0:
a, b = b, a % b
return a
print("GCD of 36 and 60 is:", find_gcd(36, 60))
print("GCD of 17 and 5 is: ", find_gcd(17, 5))端子出力
GCD of 36 and 60 is: 12
GCD of 17 and 5 is: 1段階的な実装
- 分数の簡略化と数学エンジン
- 暗号化アルゴリズム (RSA 秘密キーの生成など)
- 定期的なイベントスケジュールの設計
よくある質問
Python には GCD 関数が組み込まれていますか?
はい！ Python の標準ライブラリには、内部でコンパイルされた C 実装を使用する `math.gcd(a, b)` が含まれています。