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

╰半夏微凉° 2022-08-31 05:56 145阅读 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 条评论，145人围观）

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

相关阅读

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

> 1.正常想法关于求解，正常的想法都是：循环一个个数试验。但是，这样数据小没问题，数据大的时候，将占用内存过大无法实现，导致没有输出值。 include <

亦凉/ 2024年04月03日 14:10/ 0 赞/ 47 阅读

相关辗转相除法求最大公约数

辗转相除法，也称为欧几里德算法，用于求两个非负整数的最大公约数（Greatest Common Divisor, GCD）。算法的基本思想是：假设有两个非负整数 a 和 b

Myth丶恋晨/ 2024年02月19日 07:41/ 0 赞/ 10 阅读

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

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

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

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

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

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

相关 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 赞/ 146 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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