Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonで2つの数の公約数を求めるプログラムの書き方

はじめに

この記事では、以下の問題文に対する解決方法について学んでいきます。

問題文

2つの整数が与えられたとき、それらに共通する約数(公約数)の個数を表示する必要があります。

アプローチの考え方

まず、入力として受け取った2つの数のうち、小さい方の値(最小値)を計算します。続いて、1からその最小値までの各値で2つの数を順番に割っていき、両方の数を割り切ることができるかどうかをループ処理で確認します。

条件が真(True)と評価されるたびに、カウンターを1ずつ増加させます。最終的なカウンターの値が、2つの数の公約数の個数となります。

実装例

それでは、以下のコードで実際の実装を見てみましょう。

a = 5
b = 45
count = 0
for i in range(1, min(a, b)+1):
    if a%i==0 and b%i==0:
        count+=1
print(count)

出力結果

2

この例では、5と45の公約数は「1」と「5」の2つであるため、出力結果は「2」となります。

すべての変数はローカルスコープ内で宣言されており、それぞれの参照関係は上記のコードから確認できます。

まとめ

この記事では、Pythonを使って2つの数の公約数を求めるプログラムについて解説しました。このロジックは、ユークリッドの互除法などによる最大公約数(GCD)の計算にも応用できる基本的な手法ですので、ぜひ理解を深めておきましょう。

  1. Pythonでフィボナッチ数を求める方法：再帰と動的計画法の2つのアプローチを徹底解説

    本記事では、「n番目のフィボナッチ数を計算する」という問題に対する解決策と考え方を、2つの異なるアプローチ（再帰的手法と動的計画法）のコード例とともにわかりやすく解説します。 問題の概要 今回の課題は、n番目のフィボナッチ数を求めることです。 フィボナッチ数列 Fn は、次の漸化式によって定義されます。 Fn = Fn-1 + Fn-2 初期値（シード値）は以下の通りです。 F0 = 0、F1 = 1 この問題を解くには、主に次の2つの方法があります。 再帰的なアプローチ 動的計画法によるアプローチ アプローチ1：再帰的な手法 まずは、定義そのものをそのままコードに反映させた再帰的な実

  2. Pythonで複数の数値や配列の最大公約数（GCD）を求める方法

    本記事では、以下の問題に対する解決策について詳しく解説します。問題の概要与えられた数値の配列から、それらすべての最大公約数（GCD）を求める必要があります。アプローチ2つより多い数値の最大公約数を求める場合、GCDは引数として渡されたすべての数値に共通する素因数の積と等しくなります。これは数学的な定義に基づく方法ですが、実装がやや複雑になります。もう一つの方法として、2つの数値ずつペアでGCDを繰り返し計算するという手法があります。具体的には、最初の2つの数値のGCDを求め、その結果と次の数値のGCDを計算し、これを配列の最後まで繰り返します。本記事では、後者のアプローチを実装していきます。実