对于如何求解两个正整数的最大公约数和最小公倍数,在小学我们就接触了短除法,不过这种方法不易于转变为普适的算法。直到高中时,数学课本中有了算法的章节,其中就有了两个经典的算法——“辗转相除法”和“更相减损术”(如果忘记了,请自己百度下,也可以通过下面的例子总结规律。)——这两个是不错的求解最大公约数的方法,而且易于用计算机语言实现!(这是我在大学接触编程后才发现的。)
下面为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, 李德涛博客. 版权所有.