用短除法求最大公因数和公倍数,短除法求最大公因数全过程

首页 > 教育培训 > 作者:YD1662023-10-27 04:36:53

两个正整数a,b的最大公约数为p,记作:(a,b)=p;最小公倍数为q,记作:[a,b]=q.

例1.求24和30的最大公约数及最小公倍数。

解:对于比较简单的数,可以直接观察出它们的公因数,适合用短除法:

1) 先用24和30的公因数2分别去除两个数24,30,得商12和15;

2) 再用12和15的公因数3分别去除12,15,得商4和5;

3) 4和5已经没有比1大的公因数了,短除法结束。

用短除法求最大公因数和公倍数,短除法求最大公因数全过程(1)

因为两个公因数2和3 之积为:2*3=6,所以24和30的最大公约数为:(24,30)=6。

又因为所有公因数以及最后的商之积为:2*3*4*5=120,

所以24和30的最小公倍数为:[24,30] =120。

例2.求221和493的最大公约数及最小公倍数。

解:对于不易观察出公因数的数,可以用辗转相除法:

  1. 用较大的数除以较小的数并求出余数得:493/221=2,余数为51;
  2. 把上面的除数作为被除数,余数作为除数,再求余数得:221/51=4,余数为17;
  3. 再把上面的除数作为被除数,余数作为除数,求余数得:51/17=3,余数为0.

当余数为0时,倒数第二个余数就是这两个数的最大公约数。所以,221和493的最大公约数为:(221,493)=17。

又因为两个数a,b的最大公约数p与最小公倍数q之积pq,等于这两个数之积ab。所以q=(ab)/p.

所以,221余493的最小公倍数为:[221,493]=221*493/17=6409.

用C语言编程如下:

//求两个数a,b的最大公约数p及最小公倍数q

#include <stdio.h>

int main () //注:两个数的最大公约数与最小公倍数之积=这两个数的乘积,即pq=ab,所以q=ab/p

{ int gys(int,int); //函数原型:求最大公约数

int a,b,p;

printf("请输入两个整数:a b(两数用空格隔开):"); scanf("%d %d",&a,&b);

p=gys(a,b);//调用函数求a,b的最大公约数P

printf("(%d,%d)=%d,",a,b,p); //输出最大公约数

printf("[%d,%d]=%d",a,b,a*b/p); //输出最小公倍数(因pq=ab,所以q=ab/p)

}

//求最大公约数函数:

int gys(int x,int y) //函数首部行 ,这里x,y为形式参数

{ int r=1;//使r不为0

while(r!=0) //辗转相除:

{ r=x%y;//求余

x=y;y=r;//辗转

}

return (x); //返回最大公约数x

}

栏目热文

文档排行

本站推荐

Copyright © 2018 - 2021 www.yd166.com., All Rights Reserved.