首页 > 试题广场 >

一行代码求两个数的最大公约数

[编程题]一行代码求两个数的最大公约数
  • 热度指数：1181 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定两个不等于0的整数M和N，求M和N的最大公约数。


输入描述:
输入有两个整数。分别表示M, N


输出描述:
一个整数表示M, N的最大公约数
示例1

输入

6 12

输出

6
示例2

输入

2 3

输出

1

备注:
算法知识视频讲解
添加回答
pein531头像 pein531
辗转相除法 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int a = Integer.parseInt(params[0]), b = Integer.parseInt(params[1]);
        if(a < b){
            int temp = a;
            a = b;
            b = temp;
        }
        int remain = a % b;
        while(remain > 0){
            a = b;
            b = remain;
            remain = a % b;
        }
        System.out.println(b);
    }
}
根据代码中循环的自相似性，直接用递归函数实现，核心代码改成一行 
import scala.io.StdIn

object Main {
    def main(args: Array[String]): Unit = {
        val in = StdIn
        val params = in.readLine().split(" ")
        var a = params(0).toInt
        var b = params(1).toInt
        println(gcd(a, b))
    }
    
    def gcd(a: Int, b: Int): Int = {
        if(b == 0) a else gcd(b, a % b)
    }
}

编辑于 2021-11-20 19:05:25 回复(0)
jyu_昇而不息头像 jyu_昇而不息
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m,n;
    cin>>m>>n;
    cout<<__gcd(m,n);
}//不整那些虚的，c++库文件本身就有，直接引用
发表于 2021-06-16 17:00:59 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b){
    if(a<b)
        swap(a, b);
    while(a%b){
        int t = a%b;
        a = b;
        b = t;
    }
    return b;
}

int main(){
    int n, m;
    cin>>n>>m;
    cout<<gcd(n,m)<<endl;
    return 0;
}

发表于 2020-03-10 00:18:02 回复(0)
无心2019头像 无心2019 
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
    int t;
    if(a<b)
    {
        t=a;
        a=b;
        b=t;
    }
    while(t=a%b)
    {
        a=b;
        b=t;
    }
    return b;
}
int main()
{
    int m,n;
    cin>>m>>n;
    cout<<gcd(m,n)<<endl;
    return 0;
}

发表于 2019-09-02 21:01:54 回复(0)
君阮池头像 君阮池 
#include <stdio.h>

int main() 
{
   int M = 0;
   int N = 0;
   int ret = 0;
   scanf("%d %d",&M,&N);
   int mid = M < N ? M : N;
   for(ret = mid;ret > 0;ret--)
   {
      if(M % ret == 0 && N % ret == 0)
          break;
   }
   printf("%d\n",ret);
    return 0;
}

发表于 2023-07-12 15:20:06 回复(0)
一只老风铃头像 一只老风铃
一行代码： 
int fun(int n,int m)
{
    return n>m?(n%m==0?m:fun(m,n%m)):(m%n==0?n:fun(n,m%n));
}


发表于 2020-11-19 23:14:14 回复(0)
王仙客船长头像 王仙客船长 
#include <bits/stdc++.h>

using namespace std;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int main() {
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", gcd(a, b));
    return 0;
}

发表于 2020-06-14 13:55:11 回复(0)
夏花爱秋叶头像 夏花爱秋叶 
var line=readline().split(' ').map(Number)
var min=line[0]
var max=line[1]
if(min>max){
    var tem=min;
    min=max;
    max=tem
}
while(true){
    var tem=max%min;  //8 %6=2
    if(tem==0){
        console.log(min);
        break;
    }else{
        max=min;
        min=tem;
    }
}

发表于 2020-04-18 19:47:16 回复(0)
喜欢吃火锅的哈里头像 喜欢吃火锅的哈里 
#include <cstdio>
using namespace std;
// 这一行
int gcd (int a, int b){ return b==0?a:gcd(b, a%b); }
int main()
{
    int a, b;
    scanf("%d %d", &a, &b);
    int ans = gcd(a, b);
    printf("%d\n", ans);
    return 0;
}


发表于 2019-10-30 11:19:10 回复(0)
我要收offer头像 我要收offer
使用辗转相除法 
import java.util.Scanner;
public class Main{
    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(), n = sc.nextInt();
        sc.close();
        System.out.println(mcd(m, n));
    }
    
    public static int mcd(int i, int j){//初始要求i，j均大于0

        return j == 0 ? i : mcd(j, i%j);//保证递归时第一个参数大于第二个参数，当第二个参数为0时i就是res。
    }
}


发表于 2019-09-27 17:20:28 回复(0)
大兵201903241624792头像 大兵201903241624792 
#include<iostream>
using namespace std;
//q,r是m,n的商、余数，m,n的最大公约数是n,r的最大公约数
int gcb(int m,int n){
    return n==0?m:gcb(n,m%n);
}
int main(){
    int M,N;
    cin>>M>>N;
    int res=gcb(M,N);
    cout<<res<<endl;
    return 0;
发表于 2019-08-20 21:04:16 回复(0)
Python
圣诞节的安徒生头像 圣诞节的安徒生 
def maxCommonDivisor(m, n):
    if m == 1 or n == 1 or m == n:
        return m
    #调整m,n的顺序使得m<n
    if m > n:
        m, n = n, m
    if n % m == 0:
        return m
    for i in range(1, m):
        if m % i == 0 and n % i == 0:
            commonDivisor = i
    return commonDivisor
m, n = map(int, input().split())
print(maxCommonDivisor(m, n))

辗转相除法： 
def maxCommonDivisor(m, n):
    #辗转相除法
    #调整m,n的顺序使得m<n
    if m > n:
        m, n = n, m
    if n % m == 0:
        return m
    else:
        return maxCommonDivisor(m, n%m)

m, n = map(int, input().split())
print(maxCommonDivisor(m, n))
调整m,n的顺序使用系统函数sorted，会大幅度节省运行的空间 
m, n = sorted([m, n])


编辑于 2019-08-15 09:58:47 回复(0)
提交观点

问题信息

数学 基础数学
上传者：小小
难度：
12条回答 5860浏览

热门推荐

通过挑战的用户

查看代码

相关试题

一行代码求两个数的最大公约数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号