C言語でユークリッドの互除法で最大公約数を求めるプログラムを作る。
ユークリッドの互除法は英語では「Euclidean algorithm」と表記される。
最大公約数は英語では「G.C.D(Greatest Common Divisor)」あるいは、「G.C.M (Greatest Common Measure)」である。
環境
windows10(64bit)
Borland C++ 5.5.1 for Win32
次のコードをEuclidean.cとする。
#include <stdio.h>
//G.C.D(Greatest Common Divisor) 最大公約数
int gcd(int a, int b) {
printf("a = %d, b = %d\n", a, b);
return (b == 0) ? a : gcd(b, a % b);
}
int main() {
int num1, num2, result;
printf("最大公約数を求める2つの正の整数を入力してください:\n");
scanf("%d %d", &num1, &num2);
result = gcd(num1, num2);
printf("最大公約数は %d です\n", result);
return 0;
}
コンパイルして実行する。
c:\coco_c>bcc32 Euclidean.c
Borland C++ 5.5.1 for Win32 Copyright (c) 1993, 2000 Borland
Euclidean.c:
Turbo Incremental Link 5.00 Copyright (c) 1997, 2000 Borland
c:\coco_c>Euclidean.exe
最大公約数を求める2つの正の整数を入力してください:
876
204
a = 876, b = 204
a = 204, b = 60
a = 60, b = 24
a = 24, b = 12
a = 12, b = 0
最大公約数は 12 です
c:\coco_c>
正の整数を入力しなかった場合は、再入力するように修正する。
#include <stdio.h>
//G.C.D(Greatest Common Divisor) 最大公約数
int gcd(int a, int b) {
printf("a = %d, b = %d\n", a, b);
return (b == 0) ? a : gcd(b, a % b);
}
int main() {
int num1, num2, result;
printf("最大公約数を求める2つの正の整数を入力してください:\n");
while (1) {
scanf("%d %d", &num1, &num2);
if (num1 > 0 && num2 > 0) {
result = gcd(num1, num2);
printf("最大公約数は %d です\n", result);
break;
} else {
printf("正の整数を入力してください\n");
}
}
return 0;
}
コンパイルして実行する。
c:\coco_c>bcc32 Euclidean.c
Borland C++ 5.5.1 for Win32 Copyright (c) 1993, 2000 Borland
Euclidean.c:
Turbo Incremental Link 5.00 Copyright (c) 1997, 2000 Borland
c:\coco_c>Euclidean.exe
最大公約数を求める2つの正の整数を入力してください:
-876
204
正の整数を入力してください
876
204
a = 876, b = 204
a = 204, b = 60
a = 60, b = 24
a = 24, b = 12
a = 12, b = 0
最大公約数は 12 です
c:\coco_c>
ユークリッドの互除法を割り算ではなく、引き算にすると次のようになる。
このユークリッドの互除法での引き算のアルゴリズムは、基本情報技術者試験 平成31年度 春 午前 問7で出題された。それをC言語で実装してみた。
#include <stdio.h>
//G.C.D(Greatest Common Divisor) 最大公約数
int gcd(int a, int b) {
printf("a = %d, b = %d\n", a, b);
if(a < b){
b = b - a;
return gcd(a, b);
}else if(a > b){
a = a - b;
return gcd(a, b);
}else{
//a-b = 0の場合
return a;
}
}
int main() {
int num1, num2, result;
printf("最大公約数を求める2つの正の整数を入力してください:\n");
while (1) {
scanf("%d %d", &num1, &num2);
if (num1 > 0 && num2 > 0) {
result = gcd(num1, num2);
printf("最大公約数は %d です\n", result);
break;
} else {
printf("正の整数を入力してください\n");
}
}
return 0;
}
コンパイルして実行する。
c:\coco_c>bcc32 Euclidean.c
Borland C++ 5.5.1 for Win32 Copyright (c) 1993, 2000 Borland
Euclidean.c:
Turbo Incremental Link 5.00 Copyright (c) 1997, 2000 Borland
c:\coco_c>Euclidean.exe
最大公約数を求める2つの正の整数を入力してください:
876
204
a = 876, b = 204
a = 672, b = 204
a = 468, b = 204
a = 264, b = 204
a = 60, b = 204
a = 60, b = 144
a = 60, b = 84
a = 60, b = 24
a = 36, b = 24
a = 12, b = 24
a = 12, b = 12
最大公約数は 12 です
c:\coco_c>