C言語で最大公約数と最小公倍数の計算方法を教えて！
こういった悩みにお答えします．
本記事の信頼性
- リアルタイムシステムの研究歴12年．
- 東大教員の時に，英語でOS（Linuxカーネル）の授業．
- 2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
- プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/Vyper，Java，Ruby，Go，Rust，D，HTML/CSS/JS/PHP，MATLAB，Verse（UEFN）, Assembler (x64，ARM)．
- 東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．
- 2020年1月～現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務．2022年6月～現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO．
- 最近は自然言語処理AIとイーサリアムに関する有益な情報発信に従事．
- （AI全般を含む）自然言語処理AIの論文の日本語訳や，AIチャットボット（ChatGPT，Auto-GPT，Gemini（旧Bard）など）の記事を50本以上執筆．アメリカのサンフランシスコ（広義のシリコンバレー）の会社でプロンプトエンジニア・マネージャー・Quality Assurance（QA）の業務委託の経験あり．
- （スマートコントラクトのプログラミングを含む）イーサリアムや仮想通貨全般の記事を200本以上執筆．イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり．
こういった私から学べます．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
目次
ユークリッドの互除法
ユークリッドの互除法とは，2つの自然数の最大公約数を計算するアルゴリズムです．
2つの自然数a，b（a≧b）について，aをbで割った余りをrとすると，aとbとの最大公約数はbとrとの最大公約数に等しいです．
なので，bをr（b>r）で割った余りr'，r'とrの大きい方から小さい方で割った余りr''，と繰り返し実行し，余りが0になった時の割る数がaとbの最大公約数になります．
ユークリッドの互除法は，紀元前300年頃に記されたユークリッドによる明示的に記述された最古のアルゴリズムとして知られています．
2つの自然数aとbの最小公倍数（LCM：Least Common Multiple）の計算は，最大公約数（GCD：Greatest Common Divisor）を利用すると下式になります．
$$LCM = \frac{a * b}{GCD}$$
最小公倍数は最大公約数がわかると簡単に計算できます．
C言語のユークリッドの互除法で最大公約数と最小公倍数の計算
C言語のユークリッドの互除法で最大公約数と最小公倍数の計算コードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> unsigned long gcd(unsigned long a, unsigned long b) { if (b == 0) { return a; } else if ((a % b) == 0) { return b; } else { return gcd(b, a % b); } } int main(void) { unsigned long a, b; unsigned long ret; printf("Please input two natural numbers: "); scanf("%lu%lu", &a, &b); ret = gcd(a, b); printf("gcd = %lu\n", ret); printf("lcm = %lu\n", (a * b) / ret); return 0; } |
実行結果は以下になります．
3行目の行末に6と4を入力し，これらの最大公約数が2，最小公倍数が12と正しく計算できていることがわかります．
|
1 2 3 4 5 |
$ gcc gcd_and_lcm.c $ a.out Please input two natural numbers: 6 4 gcd = 2 lcm = 12 |
拡張ユークリッドの互除法
自然数a，bの最大公約数をgcd(a,b)と表す時，拡張ユークリッドの互除法を利用して， \(ax + by = gcd(a, b)\) の解となる整数x，yの組を見つけることができます．
例えば，6，4の最大公約数を考えてみましょう．
これらの最大公約数は2になります．
$$6x + 4y = 2$$
拡張ユークリッドの互除法でxとyを計算すると，x = 1，y = -1になります．
上式にxとyを代入すると下式になり，正しいことがわかります．
$$6 * 1 + 4 * -1 = 2$$
拡張ユークリッドの互除法で最大公約数と整数解の計算
拡張ユークリッドの互除法で最大公約数と整数解の計算コードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> unsigned long exgcd(unsigned long a, unsigned long b, long *x, long *y) { unsigned long g; if (b == 0) { *x = 1; *y = 0; return a; } else { g = exgcd(b, a % b, y, x); *y -= (a / b) * *x; return g; } } int main(void) { unsigned long a, b; long x, y; unsigned long ret; printf("Please input two natural numbers: "); scanf("%lu%lu", &a, &b); ret = exgcd(a, b, &x, &y); printf("gcd = %lu\n", ret); printf("exgcd: %lu * %ld + %lu * %ld = %lu\n", a, x, b, y, ret); printf("lcm = %lu\n", (a * b) / ret); return 0; } |
実行結果は以下になります．
a，b，x，yが正しく計算できていることがわかります．
|
1 2 3 4 5 6 |
$ gcc exgcd_and_lcm.c $ a.out Please input two natural numbers: 6 4 gcd = 2 exgcd: 6 * 1 + 4 * -1 = 2 lcm = 12 |
ユークリッドの互除法を利用してオイラーのトーシェント関数の計算
ユークリッドの互除法を利用してオイラーのトーシェント関数（φ関数）を計算します．
オイラーのトーシェント関数とは，自然数nを引数に取り，1からnまでの互いに素な自然数の個数を返す関数です．
互いに素な自然数とは，自然数aとbの最大公約数が1，つまりgcd(a, b) = 1になることですので，ユークリッドの互除法が利用できます．
オイラーのトーシェント関数を計算するコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> unsigned long gcd(unsigned long a, unsigned long b) { if (b == 0) { return a; } else if ((a % b) == 0) { return b; } else { return gcd(b, a % b); } } unsigned long euler_totient(unsigned long n) { unsigned long i; unsigned long totient = 0; for (i = 1; i <= n; i++) { if (gcd(i, n) == 1) { totient++; } } return totient; } int main(void) { unsigned long n; printf("Please input a natural number: "); scanf("%lu", &n); printf("euler_totient() = %lu\n", euler_totient(n)); return 0; } |
実行結果は以下になります．
|
1 2 3 4 |
$ gcc euler_totient.c $ a.out Please input a natural number: 6 euler_totient() = 2 |
まとめ
C言語のユークリッドの互除法で最大公約数と最小公倍数の計算方法を紹介しました．
また，ユークリッドの互除法を利用してオイラーのトーシェント関数を計算しました．
ユークリッドの互除法でアルゴリズムの基本を習得しましょう！
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
