C语言求最大公约数和最小公倍数

C语言求最大公约数和最小公倍数

最大公约数：最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。Eg：求24和60的最大公约数，先分解质因数，得24=2×2×2×3，60=2×2×3×5，24与60的全部公有的质因数是2、2、3，它们的积是2×2×3=12，所以，（24、60）=12。（质因子分解法）

最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数。

求最大公约数和最小公倍数

假设两个数a,b 他们的最大公约数为m 那么a,b的最小公倍数公式为：

因为：

a=m*i

b=m*j

最小公倍数为：m*i*j=(m*i)*(m*j)/m=a*b/m

a*b/m

所以求出a,b的最大公约数就可知其最小公倍数。

更相损减法：

《九章算術·方田》作分數約簡時，提到求最大公因數方法：反覆把兩數的較大者減去較小者，直至兩數相等，這數就是最大公因數。這方法除了把除法換作減法外，與輾轉相除法完全相同。例如書中求91和49的最大公因數：

91 > 49, 91 - 49 = 42

49 > 42, 49 - 42 = 7

42 > 7, 42 - 7 = 35

35 > 7, 35 - 7 = 28

28 > 7, 28 - 7 = 21

21 > 7, 21 - 7 = 14

14 > 7, 14 - 7 = 7

7 = 7, 因此91和49的最大公因數是7

辗转相除法：

设两数为a、b(a>b)，求a和b最大公约数(a，b)的步骤如下：用a除以b，得a÷b=q......r1(0≤r1)。若r1=0，则(a，b)=b；若r1≠0，则再用b除以r1，得b÷r1=q......r2 (0≤r2）.若r2=0，则(a，b)=r1，若r2≠0，则继续用r1除以r2，……如此下去，直到能整除为止。其最后一个能够整除的除数即为(a, b)。

例如：a=25,b=15，a/b=1......10,b/10=1......5,10/5=2.......0,最后一个为被除数余数的除数就是5,5就是所求最大公约数。

C语言求最大公约数和最小公倍数

C语言代码：

#include<iostream> using namespace std; int gcd(int a,int b); int main() {

"<<y<<" is:"

is:"

}

int gcd(int a,int b) {

} int x,y,z; cout<<"input two positive integer:"; cin>>x>>y; z=gcd(x,y); cout<<"the greatest common divisor of "<<x<<" and <<z<<endl; cout<<"the least common multiple of "<<x<<" and "<<y<<" <<x*y/z<<endl; return 0; int temp; int remainder; if(b>a) { temp=a; a=b; b=temp; } remainder=a%b; while(remainder!=0) { a=b; b=remainder; remainder=a%b; } return b;

本文来源：https://www.bwwdw.com/article/tel1.html