我要招人

去企业版

首页 > 试题广场 >

最大公约数

[编程题]最大公约数

热度指数：1059 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

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

输入描述:

输入两个整数n,m, n和m的范围是 $[1,10^9]$ 。

输出描述:

求出n、m的最大公约数。

示例1

输入

3 6

输出

示例2

输入

8 12

输出

算法知识视频讲解

牛客876653680号

欧几里得算法（辗转相除法）

int GCD(int a, int b ){

if(b == 0){

return a;

}else{

return GCD(b, a % b);

}

发表于 2020-03-04 20:46:56 回复(0)

小周好饿

c++

主要就是知道最大公约数的算法

#include<iostream>
using namespace std;
int main()
{
    int a=0,b=0;
    while(cin>>a>>b)
    {
        int ret=0;
        while(b)
        {
            ret=a%b;
            a=b;
            b=ret;
        }
        cout<<a<<endl;
    }
    return 0;
}

发表于 2019-11-14 17:07:56 回复(0)

C/C++

猫猫猫1

#include<bits/stdc++.h>
using namespace std;

int GCD(int n,int m){
    if(m==0){
        return n;
    }
    else{
        return GCD(m,n%m);
    }
}

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

发表于 2022-10-06 16:21:36 回复(1)

Python

cout0

import math
a,b=str.split(input(),' ')
a=int(a)
b=int(b)
print(math.gcd(a,b))

调库。。。

发表于 2019-05-05 23:35:04 回复(0)

Java

Boss这里有只熊

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

while (in.hasNextInt()) { // 注意 while 处理多个 case

int a = in.nextInt();

int b = in.nextInt();

System.out.println(GCD(a, b));

}

public static int GCD(int a, int b) {

if (b == 0) {

return a;

}

return GCD(b, a % b);

}

发表于 2023-09-09 20:57:06 回复(0)

讲原则的柯基在创作

//欧几里得算法求解

#include<cstdio>

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

发表于 2023-04-16 00:56:28 回复(0)

我叫马牛逼

#include<stdio.h>
int main()
{
    int n=0;
    int m=0;
    scanf("%d %d",&n,&m);
    while(n%m!=0)
    {
        int tmp=n;
        n=m;
        m=tmp%m;
    }
    //走完上面的while得到的m就是最大公约数
    printf("%d",m);
}

发表于 2022-07-28 17:30:58 回复(0)

一切都会好起来的吧

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
	if(b==0){
		return a;
	}else{
		return gcd(b,a%b);
	}
}
int main(){
	int a,b,res;
	cin>>a>>b;
	cout<<gcd(a,b)<<endl;
}

发表于 2020-03-19 11:38:20 回复(0)

ePhot̶on

#include <utility>

template<typename NumType>
NumType gcd(NumType a, NumType b) {
    while (b!=0) {
        std::swap(a, b);
        b %= a;
    }
    return a;
}

template<typename NumType>
NumType stein_gcd(NumType a, NumType b) {
	NumType k = 0;
	while (a!=0 && b != 0) {
		if (b % 2 == 0) {
			if (a % 2 == 0) {
				k++;
				a /= 2; b /= 2;
			}
			else {
				b /= 2;
			}
		}
		else {
			if (a % 2 == 0) {
				a /= 2;
			}
			else {
				if (a < b) {
					std::swap(a, b);
				}
				a -= b;
			}
		}
	}
	if (a == 0) {
		a = b;
	}
	return a<<k; // 等价于a*pow(2,k)
}

编辑于 2019-08-13 16:42:24 回复(0)