Java学习之while循环案例——计算最大公约数
Java学习之while循环案例——计算最大公约数
一、基本知识
（1）两个整数的最大公约数（GCD）是能够同时被这两个数整除的最大整数。例如：4和2的最大公约数是2，16和24的最大公约数是8等等。
（2）设计算法：众所周知，求两个整数的最大公约数有多种方法：一种方法是假设求两个数m、n的最大公约数，1是其中的一个公约数，但是可能不是最大的公约数。我们就可以一次检查k（k=2，3，4…）是否是的m、n的最大公约数，直到k>m或者k>n为止。
二、案例效果图：
三、案例代码：
import java.util.Scanner;
public class GCD {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.print("请输入第一个整数:");
int m = input.nextInt();
System.out.print("请输入第二个整数:");
int n = input.nextInt();
//求m和n的最大公约数
int gcd = 1;
int k = 2;
while (k <= m && k <= n) {
if(m % k == 0 && n % k== 0)
gcd = k;
k++;
}
System.out.println(m +"和"+ n + "的最大公约数是" + gcd);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
小结：
其实，计算两数的最大公约数还是有一种效率更高的方法——辗转相除法又名欧几里算法：
（1）计算r=m%n,如果r=0,则n是最大公约数。
（2）如果r!=0,则执行m=n,n=r,再次计算r=m%n，直到r=0为止，最后一个n即为最大公约数。
————————————————
版权声明：本文为CSDN博主「崇志广勤」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_47062907/article/details/114732808