首页 > 试题广场 >

最大公约数

[编程题]最大公约数
  • 热度指数:1015 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解

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


输入描述:

输入两个整数n,m, n和m的范围是



输出描述:
求出n、m的最大公约数。
示例1

输入

3 6

输出

3
示例2

输入

8 12

输出

4
欧几里得算法(辗转相除法)
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)
#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)
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)
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)
#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)