牛客_最大公约数辗转相除法的Java实现

素颜马尾好姑娘i 2023-09-28 20:57 8阅读 0赞

### 题目链接： ###

> [题目：最大公约数][Link 1]

### 题目描述： ###

> 如果有一个自然数 a 能被自然数 b 整除，则称 a 为 b 的倍数， b 为 a 的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。

> 输入 a 和 b , 请返回 a 和 b 的最大公约数。
> 
> 进阶：空间复杂度 O(1)，时间复杂度O(logn)。

### 测试用例： ###

> 示例1:  
> 输入：3,6  
> 返回值：3

> 示例2:  
> 输入：8，12  
> 返回值：4

> 备注： a和b的范围是\[1~10^9\]

### 辗转相除法思路： ###

> 辗转相除法思路：
> 
> 1、两个数a，b，如果b为0，计算结束，a是最大公约数
> 
> 2、否则，让a除以b，a等于b，b等于余数
> 
> 3、重复上述步骤

### 题解代码： ###

import java.util.*;
    
    
    public class Solution {
        
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 求出a、b的最大公约数。
         * @param a int 
         * @param b int 
         * @return int
         */
        public int gcd (int a, int b) {
        
            // write code here
            while(b>0){
        
                int c=a%b;
                a=b;
                b=c;
            }
            return a;
        }
    }

[Link 1]: https://www.nowcoder.com/practice/cf4091ca75ca47958182dae85369c82c?tpId=0

发表评论取消回复

表情：

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

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

相关阅读

相关牛客_最大公约数辗转相除法的Java实现

题目链接： > [题目：最大公约数][Link 1] 题目描述： > 如果有一个自然数 a 能被自然数 b 整除，则称 a 为 b 的倍数， b 为 a 的约数。

素颜马尾好姑娘i/ 2023年09月28日 20:57/ 0 赞/ 9 阅读

相关【青少年编程】求最大公约数的辗转相除法

> 「青少年编程竞赛交流群」已成立（适合6至18周岁的青少年），公众号后台回复【Scratch】或【Python】，即可进入。如果加入了之前的社群不需要重复加入。 > > 我

拼搏现实的明天。/ 2022年09月16日 03:51/ 0 赞/ 211 阅读

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

描述：计算两个非负整数 p 和 q 的最大公约数：若 q 是 0，则最大公约数为 p。否则，将 p 除以 q 得到余数 r，p 和 q 的最大公约数即为 q 和 r 的最大公约

向右看齐/ 2022年08月21日 06:43/ 0 赞/ 260 阅读

相关最大公约数（辗转相除法和更相减损法）

辗转相除法的a%b运算性能较低更相减损法，当两数相差很大时运算量也会加大 include <iostream> using names

迈不过友情╰/ 2022年07月15日 06:08/ 0 赞/ 219 阅读

相关辗转相除法，辗转相减法，枚举法实现最大公约数的计算 && 求最小公倍数

题目：最大公约数和最小公倍数计算。从键盘接收两个整数，编写程序求出这两个整数的最大公约数和最小公倍数 (提示:求最大公约数可用辗转相除法，求最小公倍数的积除以最大公约数即

今天药忘吃喽~/ 2022年04月23日 23:10/ 0 赞/ 272 阅读

相关 C语言实现大整数的辗转相除法

辗转相除法，原理，先用小的一个数除大的一个数，得第一个余数；再用第一个余数除小的一个数，得第二个余数；又用第二个余数除第一个余数，得第三个余数；这

冷不防/ 2022年03月31日 14:52/ 0 赞/ 301 阅读

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

主要是依据扩展欧几里德算法中gcd(a,b)=gcd(b,a mod b) 数学证明过程：（参考百科） ![在这里插入图片描述][watermark_type_ZmFu

青旅半醒/ 2022年03月09日 00:05/ 0 赞/ 261 阅读

相关 C实现辗转相除法

目标：求最大公约数方法：利用欧几里得算法（辗转相除法）思路：如果b=0,计算结束，a就是最大公约数否则，计算a除以b的余数，让a=b，而b=余数；回到第一步。

痛定思痛。/ 2022年02月15日 05:43/ 0 赞/ 224 阅读

相关最小公倍数 //辗转相除法

include<stdio.h> include<string.h> void swap(int &x,int &y) { int

- 日理万妓/ 2021年11月02日 14:40/ 0 赞/ 370 阅读

相关辗转相除法

问题：给出两个数a和b，求出他们的最大公约数(greatest common divisor)。解法一：辗转相除法，又叫欧几里得算法。两个正整数a和b（a>b），他们的最大

不念不忘少年蓝@/ 2021年10月29日 09:50/ 0 赞/ 333 阅读