c语言——求最大公约数和最小公倍数多种方法-创新互联

一。求大公约数

1.枚举法求大公约数

思路：求两个数中的最小值，大公约数不可能大于两个数的最小数

#includeint main()
{
	int a = 0;
	int b = 0;
	int ret = 0;
	scanf("%d %d", &a, &b);
	int min = a< b ? a : b;
	for (int i = 1; i<= min; i++)
	{
		if (a % i == 0 && b % i == 0)
		{
			ret = i;
		}
	}
	printf("大公约数是%d\n", ret);
	return 0;
}

2.辗转相除法

#includeint main()
{
	int a = 0;
	int b = 0;
	scanf("%d %d", &a, &b);
	while (b)
	{
		int t = a % b;
		a = b;
		b = t;
//比如a=12，b=18 第一次t=12 a=18 b=12.第二次t=6 a=12 b=6 第三次t=0 a=6 b=0循环终止，所以大公约数是6
	}
	printf("大公约数是%d\n", a);
	return 0;
}

二。求最小公倍数

1.枚举法求最小公倍数

思路：求两个数中的大值，因为最小公倍数肯定 >= 两个数中的大值

#includeint main()
{
	int a = 0;
	int b = 0;
	scanf("%d %d", &a, &b);
	int m = a >b ? a : b;
	while (1)
	{
		if (m % a == 0 && m % b == 0)
			break;
		else m++;

	}
	printf("最小公倍数是%d\n", m);

}

2.

#includeint main()
{
	int a = 0;
	int b = 0;
	scanf("%d %d", &a, &b);
	int i = 0;
	for (i = 1; ; i++)
	{//i=1，2...表示a的几倍，保证了是a的倍数， a*i就可以表示为最小公倍数
		if (a * i % b == 0)
		{
			printf("%d\n", a * i);
			break;
		}
	}
	return 0;
}

3.用已知大公约数求最小公倍数就可以，已知两个数a，b，大公约数是c，则最小公倍数是a*b / c

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧