はじめに
この実験では、ユークリッドの互除法を用いて、C プログラムで 2 つの整数の最大公約数 (GCD) を求める方法を学びます。まず、ユーザーから 2 つの整数を取得し、次にユークリッドの互除法を適用してそれらの GCD を計算し、最後に結果を出力します。この実験は、数論と離散数学の基本的な概念をカバーし、C プログラミング言語を用いてこれらの原理を実用的に適用する方法を示します。
2 つの整数の入力
このステップでは、C プログラムでユーザーから 2 つの整数を取得し、それらの最大公約数 (GCD) を求める方法を学びます。
まず、GCD プログラム用の新しい C ファイルを作成しましょう。
cd ~/project
nano gcd.c
次に、2 つの整数を取得する以下のコードを追加します。
#include <stdio.h>
int main() {
int num1, num2;
printf("Enter the first integer: ");
scanf("%d", &num1);
printf("Enter the second integer: ");
scanf("%d", &num2);
printf("First number: %d\n", num1);
printf("Second number: %d\n", num2);
return 0;
}
コードを詳しく見てみましょう。
scanf()は、ユーザーからの整数入力を取得するために使用されます。%dは、整数用の書式指定子です。&num1と&num2は、入力値を格納する変数のメモリアドレスを渡します。
プログラムをコンパイルして実行します。
gcc gcd.c -o gcd
./gcd
実行例：
Enter the first integer: 48
Enter the second integer: 18
First number: 48
Second number: 18
ユークリッドの互除法を実装する
このステップでは、ユークリッドの互除法を実装して、2 つの整数の最大公約数 (GCD) を求めます。
以前の gcd.c ファイルを開き、GCD の計算を含めるように修正します。
cd ~/project
nano gcd.c
ユークリッドの互除法を実装したコードを更新します。
#include <stdio.h>
// ユークリッドの互除法を用いた GCD の計算関数
int calculateGCD(int a, int b) {
// 正の値にする
a = (a > 0) ? a : -a;
b = (b > 0) ? b : -b;
// ユークリッドの互除法
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int main() {
int num1, num2, gcd;
printf("Enter the first integer: ");
scanf("%d", &num1);
printf("Enter the second integer: ");
scanf("%d", &num2);
// GCD を計算する
gcd = calculateGCD(num1, num2);
printf("First number: %d\n", num1);
printf("Second number: %d\n", num2);
printf("最大公約数：%d\n", gcd);
return 0;
}
ユークリッドの互除法の実装を詳しく見てみましょう。
- このアルゴリズムは、より大きい数をより小さい数で繰り返し除算します。
- 余りを求めるために剰余演算子
%を使用します。 - 余りが 0 になるまでこのプロセスを続けます。
- 最後の 0 でない余りが GCD です。
プログラムをコンパイルして実行します。
gcc gcd.c -o gcd
./gcd
実行例：
Enter the first integer: 48
Enter the second integer: 18
First number: 48
Second number: 18
最大公約数：6
GCD の出力
このステップでは、出力結果に補足情報を加えて、GCD の結果をより分かりやすくフォーマットして出力します。
以前の gcd.c ファイルを開き、出力のフォーマットを追加します。
cd ~/project
nano gcd.c
GCD の出力を改善したコードを更新します。
#include <stdio.h>
// ユークリッドの互除法を用いた GCD の計算関数
int calculateGCD(int a, int b) {
// 正の値にする
a = (a > 0) ? a : -a;
b = (b > 0) ? b : -b;
// ユークリッドの互除法
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int main() {
int num1, num2, gcd;
printf("最大公約数 (GCD) 計算機\n");
printf("------------------------\n");
printf("最初の整数を入力してください：");
scanf("%d", &num1);
printf("2 番目の整数を入力してください：");
scanf("%d", &num2);
// GCD を計算する
gcd = calculateGCD(num1, num2);
// フォーマットされた出力
printf("\n結果:\n");
printf("最初の数： %d\n", num1);
printf("2 番目の数：%d\n", num2);
printf("GCD: %d\n", gcd);
// 説明
printf("\n説明:\n");
printf("最大公約数 (GCD) は、両方の数に余りなく割り切れる最大の正の整数です。\n");
return 0;
}
プログラムをコンパイルして実行します。
gcc gcd.c -o gcd
./gcd
実行例：
最大公約数 (GCD) 計算機
------------------------
最初の整数を入力してください: 48
2番目の整数を入力してください: 18
結果:
最初の数: 48
2番目の数: 18
GCD: 6
説明:
最大公約数 (GCD) は、両方の数に余りなく割り切れる最大の正の整数です。
主な改善点：
- タイトルと区切りを追加
- 出力を揃えてフォーマット
- GCD の概念の説明を追加
- GCD 計算ロジックは維持
まとめ
この実験では、最初に scanf() 関数を使用してユーザーから 2 つの整数を読み取る方法を学びました。次に、ユークリッドの互除法を実装して、2 つの数の最大公約数 (GCD) を計算しました。ユークリッドの互除法は、剰余がゼロになるまで剰余演算を繰り返し適用することで、効率的に GCD を求める方法です。その時点で、GCD は最後のゼロでない剰余となります。最後に、計算された GCD を出力しました。
