この記事では、C言語を使って最小公倍数を求める方法について解説します。
目次から探す
最小公倍数の求め方
最小公倍数(LCM)は、2つ以上の整数の中で最小の倍数を求める方法です。
C言語では、ユークリッドの互除法やfor文を使った方法など、さまざまなアルゴリズムがあります。
以下では、ユークリッドの互除法とfor文を使った方法について解説します。
ユークリッドの互除法
ユークリッドの互除法は、2つの整数の最大公約数(GCD)を求めるためのアルゴリズムです。
最小公倍数を求める際にも利用することができます。
ユークリッドの互除法の概要
ユークリッドの互除法の概要は以下の通りです。
- 2つの整数をaとbとします。
- aをbで割った余りをrとします。
- rが0であれば、bが最大公約数となります。
- rが0でなければ、bをrで置き換え、2番目のステップから繰り返します。
ユークリッドの互除法を使った最小公倍数の求め方
ユークリッドの互除法を使って最小公倍数を求める手順は以下の通りです。
- 2つの整数をaとbとします。
- aとbの最大公約数を求めます。
- aとbの最大公約数をgcdとします。
- aとbの最小公倍数は、(a * b) / gcd で求めることができます。
for文を使った最小公倍数の求め方
for文を使った方法では、2つの整数の最小公倍数を求めるために、1から順番に数を増やしていき、最初に見つかった最小公倍数を求めます。
for文を使った最小公倍数の求め方のアルゴリズム
for文を使った最小公倍数の求め方のアルゴリズムは以下の通りです。
- 2つの整数をaとbとします。
- iを1から順番に増やしていきます。
- a * i が b の倍数であれば、a * i が最小公倍数となります。
- 最小公倍数が見つかったら、ループを終了します。
サンプルコードの解説
以下に、for文を使った最小公倍数を求めるためのサンプルコードを示します。
#include <stdio.h>
int main() {
int a, b, i, lcm;
printf("2つの整数を入力してください: ");
scanf("%d %d", &a, &b);
for (i = 1; ; i++) {
if (i % a == 0 && i % b == 0) {
lcm = i;
break;
}
}
printf("最小公倍数は %d です。\n", lcm);
return 0;
}このサンプルコードでは、ユーザーに2つの整数を入力してもらい、for文を使って最小公倍数を求めています。
最小公倍数の求め方のまとめ
最小公倍数を求める方法として、ユークリッドの互除法とfor文を使った方法を紹介しました。
ユークリッドの互除法は最大公約数を求めるためのアルゴリズムであり、最小公倍数を求める際にも利用することができます。
for文を使った方法では、順番に数を増やしていき、最初に見つかった最小公倍数を求めます。
for文を使った最小公倍数の求め方のメリットとデメリット
for文を使った最小公倍数の求め方のメリットとデメリットを以下にまとめます。
メリット
- シンプルなアルゴリズムであり、理解しやすいです。
- ユーザーが入力した2つの整数に対して、直感的に最小公倍数を求めることができます。
デメリット
for文を使って順番に数を増やしていくため、計算量が大きくなる可能性があります。- 特に大きな数に対しては、計算時間がかかることがあります。
以上が、C言語で最小公倍数を求める方法についての解説です。
最小公倍数を求める際には、ユークリッドの互除法やfor文を使った方法を適切に選択してください。