C语言

2024-07-07 13:56| 来源: 网络整理| 查看: 265

求两个数的最大公约数的常用方法：

※“辗转相除法”，又名欧几里得算法。基本方法如下：

设两数为a和b(a>b)，用a除以b，得a÷b=q......r，若r=0 ，则最大公约数为b；若r≠0 ,则再用b÷r，得b÷r=q......r'，若r'=0，则最大公约数为r'，若r'≠0，则继续用r÷r'......直到能够整除为止，此时的除数即为最大公约数。

例如：a=99，b=18。a÷b=99÷18=5......9不能整除，则继续b÷r=18÷9=2可以整除，则此时的除数9即为a和b两数的最大公约数。

①代码如下：

#include int main() { int a = 0; int b = 0; int t = 0; scanf("%d%d", &a, &b);//99,18 while (a%b != 0){ t = a%b; a = b; b = t; } printf("最大公约数为：%d\n", b); return 0; }

首先，从键盘键入两个数a和b的值，变量t来保存余数。用while循环来判断能否整除，根据“辗转相除法”，先用第一个数a÷b再将除数b赋给a，余数赋给b，循环往复，直到能整除时结束循环，此时的除数b即为最大公约数。

（特别说明：若ab的条件了，在继续根据辗转相除的方法即可得到最大公约数。）

※拓展：求两个数的最小公倍数

关于最小公倍数与最大公约数，有这样的定理：最小公倍数×最大公约数=两数的乘积。

即：最小公倍数=两数的乘积÷最大公约数

②代码如下：

#include int main() { int a = 0; int b = 0; int t = 0; scanf("%d%d", &a, &b);//18 99 int m = a; int n = b; while (a%b != 0){ t = a%b;//余数 9 a = b;//18 b = t;//9 } printf("最大公约数为：%d\n", b);//9 printf("最小公倍数为:%d\n",m*n/b); return 0; }

首先，从键盘键入两个数a和b的值，变量t来保存余数。再设两个变量m、n来保存a、b的原值。

先根据辗转相除法求出最大公约数b'（过程同①），再由最小公倍数=两数的乘积÷最大公约数=m×n÷b'求得最小公倍数。

【本文地址】

公司简介

联系我们