このページでは、C言語での「最大公約数の求め方」について解説していきます。
まずは２つの自然数に対する最大公約数の「力まかせ」での求め方について解説し、続いて「ユークリッド互除法」での求め方について解説します。
その後、３つ以上の自然数に対する最大公約数の求め方についても解説していきたいと思います！
上述でも少し触れているように、このページでは最大公約数を求める対象となる数は自然数であることを前提として解説させていただきます（自然数は 0 を “含む” ものとします）。
Contents
力まかせで最大公約数を求める
まずは、２つの自然数に対する最大公約数について解説し、その最大公約数の求め方について解説していきます。ここではユークリッド互除法は使わず、力まかせに最大公約数を求めていきます。
すぐにユークリッド互除法を用いて最大公約数を求めたいという方は、ユークリッドの互除法で最大公約数を求める までスキップしていただければと思います。
最大公約数とは
では、最初に最大公約数について整理しておきましょう！
最大公約数（２つの自然数に 0 が含まれない場合）
２つの自然数における最大公約数とは、基本的には２つの自然数における公約数の最大の数のことを言います。
ただし、２つの自然数の両方が 0 の場合のみ上記が当てはまりません。これに関しては後述の 最大公約数（２つの自然数に 0 が含まれる場合）で解説していきます。
また、公約数とは２つの自然数における共通の約数のことです。さらに、ある自然数に対する約数とは、その自然数を割り切ることのできる自然数のことを言います。
C言語においては、割り切れるかどうかは剰余演算（%）を行うことで調べることができます。
例えば自然数 a に対し、r が約数であるかどうかは a % r == 0 が成立するかどうかを調べることで判断できます。剰余演算では、被除数（a）が除数（r）で割り切れる場合、演算結果が必ず 0 になります。
さらに、自然数 a と自然数 b に対し、r が公約数であるかどうかは a % r == 0 と b % r == 0 の両方が成立するかどうかを調べることで判断できます。
この２つの式の両方が成立するということは、a も b も r で割り切れるということですので、r は a と b の両方に共通する約数、すなわち公約数であると言えます。
そして、このページで扱う最大公約数とは、その公約数の中で最大の数のことを言います（前述の通り両方の自然数が 0 である場合を除いて）。
例えば 16 と 24 の最大公約数を考えた場合、まず 16 と 24 の公約数は 1・2・4・8 の４つになります。
どの数が 16 と 24 の公約数であるかは、前述の通り 16 と 24 それぞれに対して実際に剰余演算を行ってみることで調べることが可能です。
そして、この４つの数の中から最大のものが最大公約数となります。今回の場合は、8 ということになりますね！
最大公約数（２つの自然数に 0 が含まれる場合）
基本的に、先程のように公約数の中の最大の数が最大公約数となりますが、２つの自然数のどちらか一方にでも 0 が含まれる場合は注意が必要です。
まず、0 はどんな自然数でも割り切れる数です。つまり、0 以外のすべての自然数が約数であるということができるでしょう。
したがって、２つの自然数のうち一方のみが 0 の場合、他方の自然数の約数全てが公約数ということになります。
さらに、その公約数の中で最大の数が最大公約数となります。0 以外の自然数においては、その数そのものが最大の約数となりますので、つまりは一方の自然数が 0 の場合、他方の数そのものが最大公約数ということになります。
また、２つの自然数の両方が 0 の場合は、最大公約数は 0 とするのが正しいようです（Wikipedia より）。したがって、この場合は前述の 最大公約数 = ２つの自然数における公約数の最大の数 が成立しないので注意してください。
ただ、２つの自然数の一方のみが 0 であろうと、２つの自然数の両方が 0 であろうと、やるべきことは同じです。結局は一方の自然数が 0 と分かった際に、他方の自然数を最大公約数とすれば良いだけです。これにより、他方も 0 なのであれば自然と求まる最大公約数も 0 となります。
自然数に 0 を含めて最大公約数を求める際には、この辺りも考慮しながら実装する必要がある点もポイントになります。
スポンサーリンク
最大公約数を力まかせで求める
最大公約数をプログラムとして解く場合も、結局は上記の例で最大公約数を求めた時と同様の演算を行えば良いだけです。
要は、剰余演算を利用して２つの自然数の最大の公約数を見つけ出してやれば良いだけです。
例えば、数を 1 〜 ２つの自然数の小さい方の数 まで 1 ずつ増加させながら、その数が２つの自然数の公約数であるかどうかを調べていけば、最後に見つけた公約数が最大公約数ということになります（最大公約数は必ず ２つの自然数の小さい方の数 以下の数となる）。
逆に、数を ２つの自然数の小さい方の数 〜 1 まで 1 ずつ減少させながら、その数が２つの自然数の公約数であるかどうかを調べていけば、最初に見つけた公約数が最大公約数ということになります。
上記の両方とも、結局は総当たりで力まかせに最大公約数を見つけ出しているだけなので処理効率は悪いです。なので、特に ２つの自然数の小さい方の数 が大きな値である場合、最大公約数を求めるのに時間がかかる可能性があります。
また、最大公約数（２つの自然数に 0 が含まれる場合） で解説したように、２つの自然数のいずれか一方でも 0 の場合は、他方の自然数を最大公約数とするための処理も必要になります。
最大公約数を力まかせで求める関数
ここまで解説してきた内容に基づいて作成した「最大公約数を力まかせに求める関数」は、下記ソースコードにおける gcd 関数となります。
gcd 関数は、引数 a と引数 b で与えられる２つの自然数の最大公約数を返却値として求める関数になります。
gcd 関数内部では、i を ２つの自然数の小さい方の数 〜 1 まで 1 ずつ減少させ、最初に見つけた a と b の公約数となる i を最大公約数として返却するようにしています。
また、引数 a と引数 b のいずれか一方でも 0 の場合は他方の引数を最大公約数として返却しています。
#include <stdio.h>
unsigned int gcd(unsigned int a, unsigned int b) {
unsigned int small;
if (a == 0) {
return b;
}
if (b == 0) {
return a;
}
if (a > b) {
small = b;
} else {
small = a;
}
unsigned int ans;
for (unsigned int i = small; i > 0; i--) {
if (a % i == 0 && b % i == 0) {
ans = i;
break;
}
}
return ans;
}
int main(void) {
unsigned int x = 776;
unsigned int y = 1261;
printf("gcd(%u, %u) = %u\n", x, y, gcd(x, y));
}ユークリッドの互除法で最大公約数を求める
先程紹介した手順でも最大公約数を求めることは可能ですが、要は最大公約数となりうる全ての候補の数に対して最大公約数であるかどうかを調べていく方法ですので、処理効率が悪いです。
こういった処理効率を高めるための１つの手段が「アルゴリズムの変更」になります。そして、最大公約数を効率よく求めるアルゴリズムとしてユークリッドの互除法があります。
次は、そのユークリッドの互除法を利用して２つの自然数の最大公約数を求めていきたいと思います！
スポンサーリンク
再帰呼び出しでユークリッドの互除法を行う
ユークリッドの互除法は、Wikipedia において、下記によって２つの自然数の最大公約数を求める手法であると説明されています。
2 つの自然数
a,b(a ≧ b)について、aのbによる剰余をrとすると、aとbとの最大公約数はbとrとの最大公約数に等しいという性質が成り立つ。この性質を利用して、
bをrで割った剰余、 除数rをその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が0になった時の除数がaとbとの最大公約数となる。
引用元：Wikipedia
１段落目に注目すると、「 a と b の最大公約数」と「b と a % b の最大公約数」とが等しいということなので、２つの自然数の最大公約数を返却値として求める関数を gcd_r とすれば（２つの自然数は引数で指定される）、gcd_r(a ,b) は gcd_r(b, a % b) によって求めることができるということになります。
つまり、２つの自然数を引数 a と b で受け取る関数 gcd_r の中で、gcd_r(b, a % b) を実行することで最大公約数を求めることができることになります。関数の中から、その関数自身を呼び出すことになりますので、再帰呼び出しを行うことになります。
unsigned int gcd_r(unsigned int a, unsigned int b) {
return gcd_r(b, a % b);
}ただ、引数 a と引数 b によっては、わざわざ再帰呼び出ししなくても最大公約数が明らかな場合があります。それは引数 a と引数 b のいずれかが 0 の場合です。
この場合は、最大公約数（２つの自然数に 0 が含まれる場合） で解説したように、0 でない方の引数そのものが最大公約数となりますので、再帰呼び出しをすることなく最大公約数を求めることができます。したがって、この場合は再帰呼び出しを行う必要もなく、求めた最大公約数を返却してやれば良いです。
unsigned int gcd_r(unsigned int a, unsigned int b) {
if (a == 0) {
return b;
}
if (b == 0) {
return a;
}
return gcd_r(b, a % b);
}単に関数の中から再帰呼び出しのみを行うと、その再帰呼び出しが延々と繰り返されることになります（実際にはスタックオーバーフローが発生してプログラムが異常終了する）。
これを防ぐために、再帰関数には、関数で解く問題の答えが明らかな場合は再帰呼び出しを行わないようにする処理が必要になります。今回の場合は、それが上記の引数 a と引数 b のいずれかが 0 の場合に再帰呼び出しを行わないようにする処理となります。
上記の gcd_r の再帰呼び出しを繰り返し行なっていれば、そのうち必ず第２引数が 0 の状態で gcd_r が実行されることになり、そこで gcd_rの再帰呼び出しの繰り返しを終了することができます。
ここで利用した再帰呼び出しについては、下記ページでも詳しく解説していますので、再帰呼び出しについて詳しく知りたい方は是非下記ページを読んでみてください。
【C言語】「再帰呼び出しの動き・メリット・書き方」を迷路を解いて理解する
再帰呼び出しでユークリッドの互除法を行う関数
ここまで解説してきた内容に基づいて作成した「再帰呼び出しでユークリッドの互除法を行って最大公約数を求める関数」は、下記の gcd および gcd_r となります。gcd_r 関数はここまで解説してきた通りの内容のものになっています。
ただ、gcd_r 関数は、ユークリッドの互除法の説明にもあったように、引数 a と引数 b において a ≧ b の関係式が成立することを前提とした作りになっています。
そのため、この関係式が成立するよう gcd_r 関数実行時の引数の指定の順番の調整を行うために gcd 関数を用意し、gcd 関数の中から gcd_r 関数を実行するようにしています。
#include <stdio.h>
unsigned int gcd_r(unsigned int a, unsigned int b) {
if (a == 0) {
return b;
}
if (b == 0) {
return a;
}
return gcd_r(b, a % b);
}
unsigned int gcd(unsigned int x, unsigned int y) {
unsigned int big, small;
if (x > y) {
big = x;
small = y;
} else {
big = y;
small = x;
}
return gcd_r(big, small);
}
int main(void) {
unsigned int x = 776;
unsigned int y = 1261;
printf("gcd(%u, %u) = %u\n", x, y, gcd(x, y));
return 0;
}ループでユークリッドの互除法を行う
また、再帰呼び出しではなくループでユークリッドの互除法を行い、最大公約数を求めることも可能です。
下記の２段落目をそのまま実装すれば、ループでユークリッドの互除法を行うことになります。
2 つの自然数
a,b(a ≧ b)について、aのbによる剰余をrとすると、aとbとの最大公約数はbとrとの最大公約数に等しいという性質が成り立つ。この性質を利用して、
bをrで割った剰余、 除数rをその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が0になった時の除数がaとbとの最大公約数となる。
引用元：Wikipedia
要は、２つの自然数 a と b が与えられた時、下記を繰り返すことでユークリッドの互除法により a と b の最大公約数を求めることができます。
r = a % bを行うrの値に応じて下記の処理を行うrが0の場合：rを求めた際の除数bを最大公約数として処理終了
rが0以外の場合：a = b・b = rに更新した後に 1. に戻る
基本は上記の処理を繰り返すことで最大公約数を求めることができますが、この場合も a もしくは b のいずれか一方でも 0 の場合は、上記の処理を行なって最大公約数を求めるのではなく、他方の数をそのまま最大公約数としてやる必要があります。
スポンサーリンク
ループでユークリッドの互除法を行う関数
ここまで解説してきた内容に基づいて作成した「ループでユークリッドの互除法を行って最大公約数を求める関数」は、下記の gcd および gcd_l となります。gcd_l 関数は先程紹介した処理の流れをそのままC言語で実装したものになっています。
また、gcd 関数は、再帰呼び出しでユークリッドの互除法を行う関数 の gcd 関数同様に、gcd_l 関数の引数 a と引数 b において a ≧ b の関係式が成立するように gcd_l 関数実行時の引数の指定の順番の調整を行うための関数となります。
今回は再帰呼び出しも行わないので gcd 関数のみで最大公約数を求めるよう実装しても良かったのですが、再帰呼び出しでユークリッドの互除法を行う関数 に合わせてgcd 関数から gcd_l 関数を呼び出す形としています。
#include <stdio.h>
unsigned int gcd_l(unsigned int a, unsigned int b) {
if (a == 0) {
return b;
}
if (b == 0) {
return a;
}
while (1) {
unsigned int r = a % b;
if (r == 0) {
break;
}
a = b;
b = r;
}
return b;
}
unsigned int gcd(unsigned int x, unsigned int y) {
unsigned int big, small;
if (x > y) {
big = x;
small = y;
} else {
big = y;
small = x;
}
return gcd_l(big, small);
}
int main(void) {
unsigned int x = 776;
unsigned int y = 1261;
printf("gcd(%u, %u) = %u\n", x, y, gcd(x, y));
return 0;
}３つ以上の自然数の最大公約数を求める
ここまで２つの自然数に対する最大公約数の求め方について解説してきましたが、次は３つ以上の自然数に対する最大公約数の求め方について解説していきたいと思います。
３つ以上の自然数の最大公約数の求め方
まず、n 個の自然数の最大公約数を求める関数を gcd_n としたいと思います。この時、n = 3 の場合、つまり 3 個の自然数の最大公約数を求める gcd_3 には下記が成立します。
gcd_3(a, b, c) = gcd_2(gcd_2(a, b), c)
つまり、３つの自然数に対する最大公約数は、そのうちの２つの自然数に対する最大公約数を求め、さらに、その 結果と残った１つの自然数に対する最大公約数を求めることで得ることができます。
ということは、２つの自然数の最大公約数を求める関数さえ用意できれば、その関数を実行していくことで３つの自然数の最大公約数も求めることができるということになります。
２つの自然数の最大公約数を求める関数に関しては、下記で紹介した gcd 関数（＋ gcd_r 関数 or gcd_l 関数）がそのまま使えます。
４つ以上の自然数の最大公約数に関しても同様で、２つの自然数の最大公約数を求めていくことで求めることができます。
gcd_n(a, b, c, d,...) = gcd_2(... gcd_2(gcd_2(gcd_2(a, b), c), d) ...)
上記の式を見ると難しそうに思えますが、要は n 個の自然数の先頭の２つの自然数の最大公約数を求め、その結果と次の自然数の最大公約数を求め、その結果と次の自然数の最大公約数を求め…、といった処理を n - 1 回分繰り返せば良いだけです。最後に求めた最大公約数が、n 個の自然数の最大公約数となります。
スポンサーリンク
３つ以上の自然数の最大公約数を求める関数
ここまで解説してきた内容に基づいて作成した「３つ以上の自然数の最大公約数を求める関数」は下記の gcd_n となります。
gcd 関数と gcd_r 関数は 再帰呼び出しでユークリッドの互除法を行う関数 で紹介したものと全く同じで、２つの自然数の最大公約数を求めるための関数になります。そして、gcd_n 関数からこれらの関数を利用して３つ以上の自然数の最大公約数を求めるようにしています。
#include <stdio.h>
unsigned int gcd_r(unsigned int a, unsigned int b) {
if (a == 0) {
return b;
}
if (b == 0) {
return a;
}
return gcd_r(b, a % b);
}
unsigned int gcd(unsigned int x, unsigned int y) {
unsigned int big, small;
if (x > y) {
big = x;
small = y;
} else {
big = y;
small = x;
}
return gcd_r(big, small);
}
unsigned int gcd_n(unsigned int nums[], unsigned int n) {
if (n == 0) {
return 0;
}
unsigned int ans = nums[0];
for (int i = 1; i < n; i++) {
ans = gcd(ans, nums[i]);
}
return ans;
}
int main(void) {
unsigned int nums[] = {
1880, 1652, 980, 4444444, 48, 0
};
printf("%u\n", gcd_n(nums, sizeof(nums) / sizeof(nums[0])));
return 0;
}gcd_n 関数は n 個の自然数の最大公約数を求める関数であり（n は引数で与えられる）、n 個の自然数は配列 nums に格納されているものとしています。
gcd_n 関数では、２つの自然数の最大公約数を gcd 関数で求めることを繰り返すことで、n 個の自然数の最大公約数 ans を求めています。
具体的には、まず for ループに入る直前に ans = nums[0] を実行し、さらに for ループの最初の繰り返しにおいて ans = gcd(ans, nums[1]) を行うことで、ans と nums[1] の最大公約数を求めています。
ここで、ans には元々 nums[0] の値が格納されているので、結局ここで求められるのは nums[0] と nums[1] の２つの自然数の最大公約数ということになります。そしてその最大公約数で ans を更新しています。
さらに、次の繰り返しにおいて ans = gcd(ans, nums[2]) を行うことで、ans と nums[2] の最大公約数を求めています。
ここで、ans には元々 nums[0] と nums[1] の２つの自然数の最大公約数が格納されているので、結局ここで求められるのは nums[0] と nums[1] と nums[2] の３つの自然数の最大公約数ということになります。そしてその最大公約数で ans を更新しています。
こんな感じで、i に対する for ループの中で ans = gcd(ans, nums[i]) が実行される際には、i + 1 個の自然数の最大公約数が求められることになります。
そして、for ループの最後には i が n - 1 の状態で ans = gcd(ans, nums[i]) が実行されるわけですから、最終的には n 個の自然数の最大公約数が求められることになります。
そしてその最大公約数が格納される変数 ans を最後に return するようにすることで、n 個の自然数の最大公約数を返却できるようにしています。
また、main 関数では求めたい個数の自然数をあらかじめ配列 nums に格納しておき、引数に配列 nums と nums の要素数を指定して gcd_n 関数を実行して最大公約数を求めています。
要素数を求める際に使用している sizeof をご存知ない方は、是非下記ページを読んでみてください。sizeof は配列の要素数を求めるだけでなく、型のサイズ等を調べる際にも有用な演算子になります。
【C言語】sizeof演算子とは？sizeof演算子を利用するメリットは？
まとめ
このページでは、C言語での「最大公約数の求め方」について解説しました！
力まかせで最大公約数を求める で解説したように、最大公約数がどんな数であるかを理解しておけば、力まかせに総当たりで最大公約数を求めることが可能です。
総当たりではなく、もっと効率的に最大公約数を求めたい場合は ユークリッドの互除法で最大公約数を求める で紹介したユークリッドの互除法を利用するのが良いと思います。
また、３つ以上の自然数の最大公約数を求める でも解説したように、２つの自然数の最大公約数を求める関数さえ用意できれば、その関数を利用して３つ以上の自然数の最大公約数も簡単に求めることができます。
特にユークリッドの互除法に関しては、ほとんどのアルゴリズムの参考書で紹介される非常に有名なアルゴリズムになりますので、この機会に是非覚えておいてください！
また、最小公倍数の求め方についても下記ページで解説していますので、よろしければ是非読んでみてください。最小公約数さえ求めることができれば、最小公倍数も簡単に求めることができます！
【C言語】最小公倍数の求め方（３つ以上も可）
