Java用辗转相除法求两个整数的最大公约数

╰半夏微凉° 2022-08-31 05:56 171阅读 0赞

按照欧几里得（Euclid）的辗转相除法，gcd（a，b）有以下的性质：

1.  gcd（a，b）=gcd（b，a）
2.  gcd（a，b）=gcd（-a，b）
3.  gcd（a，0）=|a|
4.  gcd（a，b）=gcd（b，a%b），0<=a%b<b

*  ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU4MTM4NzM0_size_16_color_FFFFFF_t_70][]

**输入：**

12
    18

package com;
    import java.io.*;
    public class app4_9 {
        public static void main(String[] args)throws IOException
        {
            int a,b,k;
            String str1,str2;
            BufferedReader buf;
            buf=new BufferedReader(new InputStreamReader(System.in));
            System.out.println("请输入第一个数a=");
            str1=buf.readLine();
            a=Integer.parseInt(str1);
            System.out.println("请输入第二个数b=");
            str2=buf.readLine();
            b=Integer.parseInt(str2);
            System.out.print("gcd("+a+","+b+")=");
            do{
                k=a%b;
                a=b;
                b=k;
            }while(k!=0);
            System.out.println(a);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU4MTM4NzM0_size_16_color_FFFFFF_t_70]: /images/20220829/d6c42c89155248a9b85add89a8affaef.png

发表评论取消回复

表情：

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

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

相关阅读

相关欧几里德算法求最大公约数（辗转相除法）

//递归版本 include<stdio.h> int gcd(int a,int b) { if(b==0) {

r囧r小猫/ 2023年02月17日 06:19/ 0 赞/ 96 阅读

相关利用辗转相除法——求最大公约数（详解）

辗转相除法求最大公约数：给定两个数，求这两个数的最大公约数欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方

╰+哭是因爲堅強的太久メ/ 2022年12月24日 01:59/ 0 赞/ 332 阅读

相关 Python求最大公约数与最小公倍数（辗转相除法）

编写程序提示用户输入两个整数然后显示他们的最大公约数与最小公倍数。方法一：直接用main（）函数调用函数 def gcd(number1,number2):

深藏阁楼爱情的钟/ 2022年12月03日 09:39/ 0 赞/ 173 阅读

相关 Java用辗转相除法求两个整数的最大公约数

按照欧几里得（Euclid）的辗转相除法，gcd（a，b）有以下的性质： 1. gcd（a，b）=gcd（b，a） 2. gcd（a，b）=gcd（-a，b） 3. g

╰半夏微凉°/ 2022年08月31日 05:56/ 0 赞/ 172 阅读

相关 80x86 汇编：用辗转相除法求两个数的最大公约数

;用辗转相除法求两个数的最大公约数 ;对两个无符号字变量进行初始化，用辗转相除法求他们的最大公约数， ;将结果保存到字变量result中。

素颜马尾好姑娘i/ 2022年08月20日 02:13/ 0 赞/ 122 阅读

相关求最大公约数-辗转相除法-欧几里德算法

这是一个 Python 写的求最大公约数的算法。 a = 12 b= 42 def find_divisor(a,b):

傷城~/ 2022年08月09日 12:45/ 0 赞/ 250 阅读

相关【c语言】用辗转相除法求最大公约数和最小公倍数

include <stdio.h> include <string.h> int main() { int hcf(int,int)

た入场券/ 2022年07月28日 09:39/ 0 赞/ 247 阅读

相关求最大公约数和最小公倍数（辗转相除法）

求a b的最大公约数和最小公倍数关系：最小公倍数=a\b/最大公约数；代码： ![Center][] [Center]: /images/20220611/

桃扇骨/ 2022年06月11日 00:49/ 0 赞/ 224 阅读

相关欧几里得算法(辗转相除法）求最大公约数代码

求解最大公约数依据如下定理：gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)；两个整数的最大公约数等于其中较小的那个数

短命女/ 2022年04月17日 05:07/ 0 赞/ 345 阅读

相关求两个数的最大公约数（辗转相除法）

求最大公约数代码此代码在vs2013环境中运行。 \define \_CRT\_SECURE\_NO\_WARNINGS 1 \include<stdio.h>

缺乏、安全感/ 2022年02月22日 05:57/ 0 赞/ 197 阅读