最大公约数

1.两个正整数的最大公约数是能同时整除这两个数的最大的正整数。

(1).而当两个数相等的时候，最大公约数就等于它本身，所以一种方法就是采用递归，当两个数a和b不相等的时候，再求a-b的绝对值和较小的数的最大公约数。 代码如下：

//函数功能： 计算两个正整数的最大公约数 int MaxCommonFactor(int a, int b) { if(a==b) //当a==b,返回a或b的值均可。 { return a; } else if(a>b) MaxCommonFactor(a-b,b); else MaxCommonFactor(a,b-a); }

当然也可以不采用递归的方法，代码如下：

int MaxCommonFactor(int a, int b) { while(a-b)//利用相减法求最大公约数 { if(a>b) a=a-b; else b=b-a; } return a; }

(2)可是当数比较大的时候，消耗的时间就比较长了，故采用更快速的方法——辗转相除法。设a对b求余为m, 若m不等于0,则 a = b, b = m, 继续求余,否则 b 为最大公约数。

int MaxCommonFactor(int a, int b) { if(a<b) //将两数中较大的数给a { int temp = b; b = a; a = temp; } while(a%b) { int temp =a%b; a = b; b = temp; } return b; }

最小公倍数

2.两个正整数的最大公倍数是能同时把这两个数除尽的最小的正整数，最小公倍数可用这两个数的乘积除以最大公约数得到。

int MinCommonMultiple(int a, int b) { int x = MaxCommonFactor(a,b); return (a*b)/x; }

数据测试

主函数代码：

#include <stdio.h> #include <stdlib.h> int MinCommonMultiple(int a, int b); int MaxCommonFactor(int a, int b); int main(void) { int a, b, x,y; printf("Input two positive integers,a,b:\n"); scanf("%d,%d", &a, &b); if(a<=0||b<=0) { printf("Input error!\n"); } else { int MaxCommonFactors = MaxCommonFactor(a,b); int MinCommonMultiples = (a*b)/MaxCommonFactor(a,b); printf("MinCommonMultiple = %d\n",MinCommonMultiples); printf("MaxCommonFactor = %d\n",MaxCommonFactors); } return 0; }