最大公约数：指两个或多个整数共有约数中最大的一个。
例如：【12和24】12的约数有：1、2、3、4、6、12；24的约数有：1、2、3、4、6、8、12、24。它们共有的约数为：1、2、3、4、6、12，则12和24的最大公约数为12
最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。
例如：【3和4】3的倍数有6、9、12、15、18、21、24……；4的倍数有4、8、12、16、20、24……。它们公有的倍数有12、24……，则3和4的最小公倍数为12
用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。
如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
可以采用函数嵌套调用和递归调用进行求两个数的最大公约数和最小公倍数
c语言实现
int divisor (int a,int b)
{
int temp; //定义整型变量
if(a
python实现
a=int(input())
b=int(input())
def div(a,b):
if a
递归
C语言实现
#include
int main()
{
int a,b;
scanf("%d %d",&a,&b);
int x,y;
x=gcd(a,b);
y=mutiple(a,b);
printf("%d %d",x,y);
}
int gcd(int a,int b){
if(a%b==0){
return b;
}
else{
return gcd(b,a%b);
}
}
int mutiple(int a,int b){
int temp;
temp=gcd(a,b);
return (a*b)/temp;
}
穷举法
- 1.求最大公约数
对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除，则temp即为最大公约数。 - 2.求最小公倍数
对两个正整数a,b,如果若干个a之和或b之和能被b所整除或能被a所整除，则该和数即为所求的最小公倍数。
#include
int gcd(int a,int b){
//对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除，则temp即为最大公约数。
int temp;
temp=(a>b)?b:a;
while(temp>0){
if(a%temp==0&&b%temp==0){
break;
}
temp--;
}
return temp;
}
int mutiple(int a,int b){
int temp;
temp=gcd(a,b);
return (a*b)/temp;
}
int main()
{
int a,b;
scanf("%d %d",&a,&b);
int x,y;
x=gcd(a,b);
y=mutiple(a,b);
printf("%d %d",x,y);
}
python实现，穷举法
a=int(input())
b=int(input())
#可使用for in 循环和while循环实现
'''
def div(a,b):
temp=a if a 
