计算最大公约数和最小公倍数是简单常见的算法,他有多种方式实现,比如:穷举法、辗转相除法、相减法等等,方法很多,目的相同,下面就用其中一种方法,辗转相除法来完成这个算法,下面将用计算机编程的方式实现。
9和15最大公约数为3 最大公约数和最小公倍数的概念
最大公约数指某几个整数共有约数中最大的一个。最小公倍数是某几个整数公有的倍数中最小的一个正整数。 它们之间的关系最大公约数=两数之积/最小公倍数,所以只要求出一个另外一个自然通过简单的计算求出来了。
辗转相除法,算法举例有两整数a和b: ① a%b得余数c ② 若c=0,则b即为两数的最大公约数 ③ 若c≠0,则a=b,b=c,再回去执行① 例如求35和15的最大公约数过程为: 35÷15 余5,,15÷5余0,5即为最大公约数
代码实现
图片代码 演示结果
结果 文本代码
import java.util.Scanner; public class S { public static void main(String args[]){ Scanner s=new Scanner(System.in); int a=s.nextInt(); int b=s.nextInt(); int m=a;//用m记录a int n=b;//用n记录b int c=1;//定义余数 while(c!=0){//只要余数不等于0,就做循环 c=a%b; a=b; b=c; System.out.println(a+b+c); } System.out.println('最大公约数'+a);//此时的a是原来的b System.out.println('最小公倍数数'+m*n/a);//利用关系计算出最小公倍数 } }
结语
至此这个算法就演示完毕了,当然实现的方法好多,效率也不一样,这里只演示了一种算法,有兴趣的可以试试其他方法。 每天持续分享计算机编程知识,c语言,java,php等等,欢迎交流,一起进步,欢迎收藏,转发,关注趣IT科技,喜欢就请点个赞吧。
|