Java学习之while循环案例——计算最大公约数

桃扇骨 2022-11-08 06:05 199阅读 0赞

**一、基本知识**

（1）两个整数的最大公约数（GCD）是能够同时被这两个数整除的最大整数。例如：4和2的最大公约数是2，16和24的最大公约数是8等等。  
（2）设计算法：众所周知，求两个整数的最大公约数有多种方法：一种方法是假设求两个数m、n的最大公约数，1是其中的一个公约数，但是可能不是最大的公约数。我们就可以一次检查k（k=2，3，4…）是否是的m、n的最大公约数，直到k>m或者k>n为止。

**二、案例效果图：**  
![在这里插入图片描述][20210313103808483.png_pic_center]  
**三、案例代码：**

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）计算r=m%n,如果r=0,则n是最大公约数。  
（2）如果r!=0,则执行m=n,n=r,再次计算r=m%n，直到r=0为止，最后一个n即为最大公约数。

[20210313103808483.png_pic_center]: /images/20221023/5ebb60918e984433b0526cfa3d1ea3d9.png

发表评论取消回复

表情：

评论列表（有 0 条评论，199人围观）

还没有评论，来说两句吧...

相关阅读

相关 ##Java 计算最大公约数

题目描述下面是求两个整数n1和n2的最大公约数。首先找出n1和n2的最小值d，然后依次检验d，d-1，d-2，…，2，1是否是n1和n2的公约数。第一个满足条件的公约数就

￡神魔★判官ぃ/ 2022年12月26日 00:55/ 0 赞/ 186 阅读

相关 Java学习之求最大公约数与最小公倍数案例

案例代码： import java. util.Scanner; public class GCDLCM{ /求最大公约数(Grea

蔚落/ 2022年11月13日 09:27/ 0 赞/ 159 阅读

相关 Java学习之while循环案例——计算最大公约数

一、基本知识（1）两个整数的最大公约数（GCD）是能够同时被这两个数整除的最大整数。例如：4和2的最大公约数是2，16和24的最大公约数是8等等。（2）设计算法：众所

桃扇骨/ 2022年11月08日 06:05/ 0 赞/ 200 阅读

相关 Java学习之do-while循环及案例

一、基本知识 do-while循环的一般格式如下： [initialization] do{ //循环体 [itera

梦里梦外;/ 2022年11月07日 14:52/ 0 赞/ 213 阅读

相关 Java学习之while循环及案例

一、基本知识 1.在程序设计中，我们发现有时需要反复地执行一段相同的代码，这时就需要循环来实现了。Java中提供了4种循环结构：while循环、do-while循环、for

梦里梦外;/ 2022年11月07日 14:44/ 0 赞/ 203 阅读

相关最大公约数

什么是最大公约数 > 最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（

小灰灰/ 2022年07月29日 06:26/ 0 赞/ 197 阅读

相关最大公约数

public class GCD { //方法一 public static void gcd1(int a, int b) {

左手的ㄟ右手/ 2022年05月26日 01:28/ 0 赞/ 166 阅读

相关最大公约数

问题D：最大公约数时间限制：1秒内存限制：64 MB 提交：554解决：274 \[ [提交][Link 1] \] \[ [状态][Link 2] \] \[

末蓝、/ 2022年05月22日 12:20/ 0 赞/ 221 阅读

相关 Java趣味编程案例20----最大公约数

求任意两个数的最大公约数。 1）利用辗转相除法求最大公约数 2）利用递归求最大公约数 import java.util.Scanner; / 辗转相除法

亦凉/ 2022年04月23日 09:44/ 0 赞/ 369 阅读

相关 Java 计算公约数和最大公约数

package java_1; import java.util.Scanner; public class Exercises_3

清疚/ 2021年11月02日 09:14/ 0 赞/ 361 阅读