计算最大公约数和最小公倍数是简单常见的算法，他有多种方式实现，比如：穷举法、辗转相除法、相减法等等，方法很多，目的相同，下面就用其中一种方法，辗转相除法来完成这个算法，下面将用计算机编程的方式实现。

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科技，喜欢就请点个赞吧。