目錄

• 1 題目
• 2 分析
• • 2.1 輾轉相除法
  • 2.2 相減法
• 3 實現(xiàn)
• • 3.1 實現(xiàn)1（輾轉相除法）
  • 3.2 實現(xiàn)2（相減法）

1 題目

輸入兩個正整數(shù)m和n，求其最大公約數(shù)和最小公倍數(shù)。

2 分析

求最大公約數(shù)和最小公倍數(shù)這里給出兩種實現(xiàn)方法，實際上只用求最大公約數(shù)即可，因為在數(shù)學上最小公倍數(shù)有這樣的關系，所求的兩個數(shù)的積即為其最大公約數(shù)和最小公倍數(shù)的積，所以只求出其中一個，另一個便能直接計算出來。

注：這里只給出通俗的計算方法，并不給出嚴格數(shù)學證明過程。

2.1 輾轉相除法

輾轉相除法求兩個數(shù)的最大公約數(shù)的步驟如下，假如兩個數(shù)為 $a$ 和 $b$：

用大的數(shù) $a$ 除以小的數(shù) $b$，得第一個余數(shù) $c$；

再用上一步計算中小的那個數(shù)除以上一步中的余數(shù)，即 $b$ 除以 $c$，得第二個余數(shù) $d$；

重復上兩步；

直到余數(shù)是0為止.那么，最后一個除數(shù)就是所求的最大公約數(shù)（如果最后的除數(shù)是1，那么原來的兩個數(shù)是互質(zhì)數(shù)）

程序見實現(xiàn)3.1

2.2 相減法

假如兩個數(shù)為 $a$ 和 $b$：

若 $a>b$，則 $a=a?b$

若 $a<b$，則 $b=b?a$

若 $a=b$，則 $a$（或 $b$）即為兩數(shù)的最大公約數(shù)

若 $a$ ≠ $b$，則再回去執(zhí)行第一步

程序見實現(xiàn)3.2

3 實現(xiàn)

3.1 實現(xiàn)1（輾轉相除法）

#include <stdio.h>int main() {int n, m;int temp;printf("請輸入n和m，中間用空格分隔：");scanf("%d%d", &n, &m);// 將較大的那個數(shù)賦值給a，較小的那個數(shù)賦值給bif (m > n) {temp = m;m = n;n = temp;}int a = n;int b = m;// 利用輾轉相除法計算最大公約數(shù)while (b != 0) {temp = a % b;a = b;b = temp;}printf("最大公約數(shù)是%d\n", a);printf("最小公倍數(shù)是%d\n", n * m / a);return 0; }

3.2 實現(xiàn)2（相減法）

#include <stdio.h>int main() {int a, b ;printf("請輸入a和b，中間用空格分隔：");scanf ("%d%d", &a, &b);int m = a;int n = b; // 當a, b不相等，用大數(shù)減小數(shù)，直到相等為止while (a != b) {if (a > b) {a = a - b;} else {b = b - a;}}printf("最大公約數(shù)是%d\n", a);printf("最小公倍數(shù)是%d\n", m * n / a); }

總結

以上是生活随笔為你收集整理的C语言经典例16-最大公约数和最小公倍数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。