最大公约数和最小公倍数问题

[realDuYuanChao]

求解最大公约数和最小公倍数

什么是最公约数

最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个

什么是最大公倍数

两个或多个整数公有的倍数叫做它们的公倍数

暴力破解法

#include<stdio.h>

void swap(int *pa, int *pb){
	int t = *pa;
	*pa = *pb;
	*pb = t;
}
int main(){

	printf("请输入第一个数:");
	int a;
	scanf("%d", &a);

	printf("请输入第一个数:");
	int b;
	scanf("%d", &b);

	//保证a <= b
	if(a < b){
		swap(&a, &b); //交换a,b的值
	}

	//求解最大公约数
	int max = 1;
	for(int i = 1; i <= b; i++){
		if(a % i == 0 && b % i == 0){
			max = i; //求解最大的公约数
		}
	}
	printf("最大公约数:%d\n", max);

	//求解最小公倍数
	int min = a;
	while(1){
		if(min % a == 0 && min % b == 0){
			break; //找到了最小公倍数
		}
		min++;
	}
	printf("最小公倍数:%d\n", min);
	return 0;
}

输入

请输入第一个数:12
请输入第一个数:16

输出

最大公约数:4
最小公倍数:48

数学定理

最大公约数 * 最小公倍数 = 两数之积

所以根据这个数学定理,我们只需要求出最大公约数，就可以通过定理推出最小公倍数，改进后的代码如下

#include<stdio.h>

void swap(int *pa, int *pb){
	int t = *pa;
	*pa = *pb;
	*pb = t;
}
int main(){

	printf("请输入第一个数:");
	int a;
	scanf("%d", &a);

	printf("请输入第二个数:");
	int b;
	scanf("%d", &b);

	//保证 a <= b
	if(a < b){
		swap(&a, &b); //交换a,b
	}

	//求最大公约数
	int max = 1;
	for(int i = 1; i <= b; i++){
		if(a % i == 0 && b % i == 0){
			max = i; //Çó½â×î´óµÄ¹«Ô¼Êý
		}
	}
	printf("最大公约数:%d\n", max);

	//求最小公倍数
	printf("最小公倍数:%d\n", a * b / max);
	return 0;
}

算法优化

#include<stdio.h>

void swap(int *pa, int *pb){
    int t = *pa;
    *pa = *pb;
    *pb = t;
}
int main(){
    printf("请输入第一个数:");
    int a;
    scanf("%d", &a);

    printf("请输入第二个数:");
    int b;
    scanf("%d", &b);

    //保证 a <= b
    if(a < b){
        swap(&a, &b); //交换a,b
    }
    int multi = a * b; //保存a和b的值
    while (a % b != 0){
        int t = a % b;
        a = b;
        b = t;
    }
    printf("最大公约数:%d\n", b);
    printf("最小公倍数:%d\n", multi / b);

    return 0;
}