首先我们得先搞清楚大公约数和最小公倍数的定义.
大公约数:两个或多个整数共有约数中大的一个,例如,6和9的大公约数是3.
最小公倍数:两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数,例如,6和21的最小公倍数是42.
一.辗转相除法.
有两个整数a和b
1.a%b = temp; 若temp=0;此时b就是a和b的大公约数
2.若b≠0,则a=b;b=temp;继续a%b的操作
3.例如.21和6, 21%6余3; 6%3余0;此时3就是他们的大公约数
4.得到大公约数后,用这两个数的乘积除以他们的大公约数就得到了最小公倍数,例如,6和21,大公约数为3, (6*21)/3 = 42; 42就是他们的最小公倍数.话不多说上代码
#define _CRT_SECURE_NO_WARNINGS 1
#include//辗转相除法,乘积除以大公因数得到最小公倍数
int fib(int a, int b)
{
while (a*b!=0)
{
int tmp = a % b;
a = b;
b = tmp;
}
//printf("%d %d\n", a, b);
return a;
}
int main()
{
int a = 0;
int b = 0;
printf("请输入两个数:>\n");
scanf("%d %d", &a, &b);
int sum = a * b;
int m = fib(a,b);
printf("大公约数 = %d\n", a);
printf("最小公倍数 = %d\n",sum/m);
return 0;
} 运行结果
二.更象相减
1. 若a >b,则 a = a - b；
2. 若a< b,则 b = b - a；
3. 若 a = b,则 a(b)即为两数的大公约数
4.若 a ≠ b,则继续执行第一步操作。
5.例如21和6. 21-6=15(15>6); 15-6=9(9>6); 9-6=3(3<6); 6-3=3(3=3)// 3就是这两个数的大公约数,同理,同样的办法可以得到两个数的最小公倍数,上代码
int fib(int a, int b)
{
while (a != b)
{
if (a >b)
{
a = a - b;
}
else
{
b = b - a;
}
}
return a;
}
int main()
{
int a = 0;
int b = 0;
printf("请输入两个数;>\n");
scanf("%d %d", &a, &b);
int sum = a * b;
int m = fib(a, b);
printf("大公约数 = %d\n", m);
printf("最小公倍数 = %d\n", sum/m);
return 0;
}运行结果
三.硬算(穷举).
有两个整数a和b：
从1开始,让a和b同时除以,直到某个数同时满足被a和b整除,此时这个被整除的数字就是大公约数,同样道理,可以获得最小公约数.上代码
int fib(int a, int b)
{
int n = 0;
for (int i = 1; i< b; i++)//i小于a和b任意一个都行
{
if ((a % i == 0) && (b % i == 0))
{
n = i;
}
}
return n;
}
int main()
{
int a = 0;
int b = 0;
printf("请输入两个数;>\n");
scanf("%d %d", &a, &b);
int sum = a * b;
int m = fib(a, b);
printf("大公约数 = %d\n", m);
printf("最小公倍数 = %d\n", sum/m);
return 0;
}运行结果
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
