目录
❤️1.穷举法：
最大公约数：
思路：
最小公倍数：
思路：
❤️2.辗转相除法：
最大公约数与最小公倍数：
最大公约数思路：
最小公倍数思路：（公式）
❤️3.特殊方法：
最大公约数：（相减法：）
思路：
最小公倍数：（叠乘法：）
思路：
总结：
❤️1.穷举法：
最大公约数：
思路：
假设两个数字a和b，比较出更小的数字赋值给变量min，遍历1到min的整数，找到所有能共同被a和b整除的数字，其中数值最大的便是所求最大公约数。
//穷举法
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d %d",&a,&b);
int min = (a < b ? a : b);
while (a % min != 0 || b % min != 0)//如果不能同时整除
{
min--;
}
printf("%d",min);
return 0;
}
最小公倍数：
思路：
已知两个数的最小公倍数大于等于两个数的最大值，所以可以先求出两个数的较大值max，用max分别试除两个数，如果能整除，max即为两个数的最小公倍数；不能整除，让max=max+1直到找到最小公倍数为止。
//穷举法
#include<stdio.h>
int main()
{
int x = 0;
int y = 0;
scanf("%d %d",&x,&y);
int max = (x > y ? x : y);//取最大值
while (max%x != 0 || max%y!= 0)//如果不能同时整除
{
max++;//每次增加1
}
printf("%d",max);
return 0;
}
❤️2.辗转相除法：
最大公约数与最小公倍数：
最大公约数思路：
假设两个数字a和b，求两个数字相除的余数c=a%b，如果余数为0，则b为最大公约数。如果b不为零，a=b,b=c,继续循环计算。
最小公倍数思路：（公式）
两个数的最小公倍数数等于两个数的乘积除以两个数的最大公约数。即：x，y的最小公倍数 min(公倍数)=x*y÷max(公约数)
//辗转相除法
#include <stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d %d", &a, &b);
int z = a * b;
//求最大公约数：
int c = 0;
while (a % b != 0)
{
c = a % b;
a = b;
b = c;
}
printf("最大公约数为：%d\n", b);
//求最小公倍数：
int min = z / b;
printf("最小公倍数：%d\n", min);
return 0;
}
❤️3.特殊方法：
最大公约数：（相减法：）
思路：
假设两个数字a和b，如果a>b，则a=a-b;如果b>a,则b=b-a。一直循环计算直到a=b，则此时a、b的值即为所求最大公约数。
//相减法
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d %d",&a,&b);
while (a != b)//直到两个数相等
{
if (a > b)
{
a = a- b;
}
else
{
b = b - a;
}
}
printf("%d",a);
return 0;
}
最小公倍数：（叠乘法：）
思路：
已知两个数的公倍数一定与这两个数存在倍数关系，那么求解最小公倍数我们就可以将其中一个数依次扩大1倍、2倍、3倍……直到出现第一个扩大n倍的数可以同时整除这两个数，这个数就是最小公倍数。
//迭乘法
#include<stdio.h>
int main()
{
int x = 0;
int y = 0;
scanf("%d %d",&x,&y);
int i = 1;
while (x * i %y != 0)
{
i++;
}
printf("%d",x*i);
return 0;
}
总结：
计算最大公约数与最小公倍数的时候，优先推荐辗转相除法与两种特殊方法，效率高！！！
