大家好,又见面了,我是你们的朋友全栈君。
求两个数的最大公约数的常用方法:
※“辗转相除法”,又名欧几里得算法。基本方法如下:
设两数为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 <stdio.h>
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即为最大公约数。
(特别说明:若a<b,例如a=18,b=99。t=a%b=18;a=99;b=t=18。我们发现通过一次循环交换了a、b的值,这时就能满足a>b的条件了,在继续根据辗转相除的方法即可得到最大公约数。)
※拓展:求两个数的最小公倍数
关于最小公倍数与最大公约数,有这样的定理:最小公倍数×最大公约数=两数的乘积。
即:最小公倍数=两数的乘积÷最大公约数
②代码如下:
#include <stdio.h>
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’求得最小公倍数。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/145408.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...