用C语言，求解两个正整数（至少一个为合数）的最大公约数和最小公倍数

对于如何求解两个正整数的最大公约数和最小公倍数，在小学我们就接触了短除法，不过这种方法不易于转变为普适的算法。直到高中时，数学课本中有了算法的章节，其中就有了两个经典的算法——“辗转相除法”和“更相减损术”(如果忘记了，请自己百度下，也可以通过下面的例子总结规律。)——这两个是不错的求解最大公约数的方法，而且易于用计算机语言实现！（这是我在大学接触编程后才发现的。）
下面为6和10求最大公约数2的过程：

辗转相除法：
10 = 1 * 6 + 4;
6  = 1 * 4 + 2;
4  = 2 * 2 + 0;
2为6和10的最大公约数。 更相减损术： 10 – 6 = 4;
6  – 4 = 2;
4  – 2 = 2;
2为6和10的最大公约数。

只要求解出了最大公约数，求解最小公倍数将变得十分简单，可以使用一下公式：

MAX_yue * MIN_bei = A * B;
其中，A、B为两个正整数，MAX_yue为A和B的最大公约数，MIN_bei为A和B的最小公倍数。

下面将是用C语言实现“求解两个正整数（这里限定为：至少有一个数为合数。原因很简单，如果两个值都为素数，那么这两个值一定互为素数，如果使用下面的算法计算，效率会比较低。当然，可以先判断这两个数是否为素数，如果都为素数就不再计算，直接输出结果！）的最大公约数和最小公倍数”算法的源码，仅供参考！

//求两个正整数的最大公约数和最小公倍数
#include<stdio.h>
#include<stdlib.h>	//此库包含清屏函数：system("CLS");

//用辗转相除发求两个数的最大公约数
int get_MAX_yue_zhanzhuan(int num1,int num2){
	int a = num1,b = num2;
	int MAX_yue;
	int t;	//t为中间变量，一是用于数据交换，而是用于存放临时结果

	//确保a大于b
	if(a < b){
		t = a;
		a = b;
		b = t;
	}

	//辗转相除法算法核心代码
	t = a % b;
	while(t != 0){
		a = b;
		b = t;
		t = a % b;
	}

	printf("使用“辗转相除法”计算，%d和%d的最大公约数为：%dn",num1,num2,b);

	return b;
}

//有更相减损术求两个数的最大公约数
int get_MAX_yue_gengxiang(int num1,int num2){
	int a = num1,b = num2;
	int MAX_yue;
	int t;	//t为容器变量

	//确保a大于b
	if(a < b){
		t = a;
		a = b;
		b = t;
	}

	//更相减损术算法核心代码
	t = a - b;
	while(t != 0){
		a = b >= t ? b : t;
		b = b < t ? b : t;
		t = a - b;
	}

	printf("使用“更相减损术”计算，%d和%d的最大公约数为：%dn",num1,num2,b);
	return b;
}

//求两个数的最小公倍数
void get_MIN_bei(int num1,int num2,int MAX_yue){
	int MIN_bei;

	MIN_bei = num1 * num2 / MAX_yue;

	printf("%d和%d的最小公倍数为：%dn",num1,num2,MIN_bei);
}

void main(){
	int num1 = 1,num2 = 1,MAX_yue;
	int con = 0;	//作为选项控制变量的容器
	int has_yue = 0;//判断是否已经计算过最大公约数，是为1，否则为0

	//启动系统
	while(1){
		//控制台展示
		printf("***********************************************************n");
		printf("录入（重新录入）数据，请键入：0n");
		printf("使用“辗转相除法”计算最大公约数，请键入：1n");
		printf("使用“更相减损术”计算最大公约数，请键入：2n");
		printf("计算最小公倍数，请键入：3n");
		printf("退出系统，请键入：4n");
		printf("***********************************************************n");
		printf("控制码为：");

		//获取控制指令
		scanf("%d",&con);
		system("CLS");

		//实现控制
		if(con < 0 || con > 4){
			printf("控制码无效，请重新输入!n");
			continue;
		}

		switch(con){
			case 0 :
				printf("请输入第一个正整数（大于2的正整数）：");
				scanf("%d",&num1);
				printf("请输入第二个正整数（大于2的正整数）：");
				scanf("%d",&num2);
				has_yue = 0;
				break;
			case 1 :
				if(num1 == 1 || num2 == 1){
					printf("还未录入数据，请先执行0n");	
				}else{
					MAX_yue = get_MAX_yue_zhanzhuan(num1,num2);
					has_yue = 1;
				}
				break;
			case 2 :
				if(num1 == 1 || num2 == 1){
					printf("还未录入数据，请先执行0n");	
				}else{
					MAX_yue = get_MAX_yue_gengxiang(num1,num2);
					has_yue = 1;
				}
				break;
			case 3 :
				if(has_yue == 1){
					get_MIN_bei(num1,num2,MAX_yue);
				}else{
					printf("还未计算最大公约数，请先执行1或者2n");
				}
				break;
			default :
				break;
		}

		if(con == 4){
			break;
		}
	}

}

© 2013 – 2015, 李德涛博客. 版权所有.