最大公约数:用欧几里得辗转相除法,两个数a,b while(b > 0) { t = a % b; a = b; b = t; } 循环结束后的a 就是最大公约数 里 a = 5, b = 8 ①b > 0 进入循环 t = 5 % 8 = 5; a = b = 8; b = t = 5; ②b = 5 > 0进入循环 t = 8 % 5 = 3; a = b = 5; b = t = 3; ③b = 3 > 0进入循环 t = 5 % 3 = 2; a = b = 3; b = t = 2; ④b = 2 > 0进入循环 t = 3 % 2 = 1; a = b = 2; b = t = 1; ⑤b = 1 > 0进入循环 t = 1 % 2 = 0; a = b = 1; b = t = 0; ⑥b = 0退出循环 循环结束最大公约数为a = 1;
最小公倍数:利用两个数的最大公约数和最小公倍数的乘积等于这两个数的乘积 比如 2 * 4 = 2 * 4; 3 * 5 = 1 * 15; 4 * 6 = 2 * 12;
下面是代码:
# include "stdio.h"
int yue(int a, int b);
int bei(int a, int b, int max);
int main()
{
int a, b;
int min,max;//max是最大公约数,min是最小公倍数
scanf ("%d %d",&a, &b);
max = yue(a, b);
min = bei(a, b, max);
printf("%d %d", max, min);
return 0;
}
int yue(int a, int b)
{
int t;
while(b > 0)
{
t = a % b;
a = b;
b = t;
}
return a;
}
int bei(int a, int b , int max)
{
return a * b / max;
}
|