首页 > 试题广场 >

最大公约数

[编程题]最大公约数

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

输入两个正整数，求其最大公约数。

输入描述:

测试数据有多组，每组输入两个正整数。

输出描述:

对于每组输入,请输出其最大公约数。

示例1

输入

49 14

输出

算法知识视频讲解

Java

中南的小菜鸡

import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
int y =sc.nextInt();

int temp;

if(x>y){
temp = x;
x = y;
y = temp;
}
int m;
while(y%x != 0){
m=x;
x=y%x;
y=m;
}
System.out.println(x);
}
}

发表于 2018-08-03 01:21:01 回复(0)

宋朝栗子

#include<stdio.h>

int main()
{
    int a, b, tmp;
    while(scanf("%d %d", &a, &b) == 2){
        if(a > b){
            tmp = a;
            a = b;
            b = tmp;
        }
        while(a % b != 0){
            tmp = a % b;
            a = b;
            b = tmp;
        }
        printf("%d\n", b);
    }
    return 0;
}

发表于 2018-07-21 11:27:40 回复(0)

Python

华科平凡

def gcd(a, b):
    if a < b:
        a, b = b, a

    while b != 0:
        temp = a % b
        a = b
        b = temp

    return a

while True:
    try:
        a, b = map(int, input().split())
        print(gcd(a, b))
    except:
        break

本来准备使用math库的，没想到被ban了？？

发表于 2017-10-01 10:22:46 回复(0)

Java

AllenHua

import java.util.Scanner;

/**
 * @author Allen_Hua
 * @create_time 创建时间：May 13, 2018 1:45:43 PM 类说明
 */
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            int a = scan.nextInt();
            int b = scan.nextInt();
            System.out.println(gcd(a, b));
        }
    }
    //辗转相除法求最大公约数 greatest common divisor
    private static int gcd(int a, int b) {
        // TODO Auto-generated method stub
        int max, min, temp;
        //将a、b中的较大值给max 较小值给min
        if (a > b) {
            max = a;
            min = b;
        } else {
            min = a;
            max = b;
        }
        temp = max % min;//大值对小值取模
        while (temp != 0) {
            max = min;
            min = temp;
            temp = max % min;
        }
        return min;
    }
}

发表于 2018-05-13 13:59:41 回复(0)

huangju

#include <stdio.h>

int gcd(int a,int b){//非递归

    while(b){
    int t=a%b;
    a=b;
    b=t
    }
    return a;

}

int gcd(int a,int b){//递归
return b==0? a:gcd(b,a%b);
}
int main(){
int a,b;
while(scanf("%d %d",&a,&b)!=EOF)printf("%d\n",gcd(a,b));
return 0;
}

发表于 2018-01-17 22:37:29 回复(0)

已注销

//最近闲的慌，跑来刷考研题目，O(∩_∩)O哈哈~
#include<iostream>
using namespace std;
int gcd(int m,int n)
{
    return ((m>=n)?(m%n==0?n:gcd(n,m%n)):(n%m==0?m:gcd(m,n%m)));
}
int main()
{
    int m,n;
    while(cin>>m>>n)
    {
        cout<<gcd(m,n)<<endl;
    }
    return 0;
}

发表于 2016-08-12 15:20:24 回复(0)

viod

求最大公约数常用更相减损术或辗转相除法：

#include<stdio.h>
int main(){
    long n,m;
    scanf("%ld %ld",&n,&m);
    while(n&&m){
        if(n>m) n %= m;
        else m %= n;
    }printf("%ld\n",n>m?n:m);
}

发表于 2021-06-06 22:46:30 回复(0)

C/C++

拜托求求给一个offer

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
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;
    while (cin >> a >> b)
    {
        cout << GCD(a, b) << endl;
    }
    return EXIT_SUCCESS;
}

发表于 2021-02-19 09:46:21 回复(0)

胡桃夹子🎈

#include<iostream>
using namespace std;
int main()
{
	int a, b;
	while (cin>>a>>b)
	{
		while (b != 0)//辗转相除法，例如49 21
		{
			int t = b;//21、7
			b = a % b;//7、0。下一个a是上一个b,下一个b是当前a mod b
			a = t;//21、7
		}
		cout << a << endl;
	}
	return 0;
}

辗转相除法

编辑于 2020-05-05 11:40:42 回复(0)

IceCapriccio

#include <iostream>
(720)#include <algorithm>

using namespace std;

int main() {
    int a, b;
    while (cin >> a >> b) {
        cout << __gcd(a, b) << endl;
    }
    return 0;
}

algorithm头文件里有已经写好的最大公因数的函数😉

发表于 2020-03-10 19:46:31 回复(2)

C/C++

大内高手

#include<iostream>
#include<cstdio>

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;
    while(cin>> a >> b)
    {
        cout<< GCD(a, b) <<endl;
    }
    return 0;
}

非常经典的欧几里得算法求最大公约数，也叫辗转相除法，即a和b的最大公约数等于b和a%b的最大公约数。

编辑于 2020-03-05 13:46:45 回复(0)

C/C++

斯巴达12138

#include<iostream>
using namespace std;
int gcd(int a,int b){
    return !b?a:gcd(b,a%b);
}
int main(){
    int a,b;
    while(cin>>a>>b){
        int res=gcd(a,b);
        cout<<res<<endl;
    }
}

发表于 2020-03-04 10:54:13 回复(0)

C/C++

idutura

/*
    辗转相除法
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    while(cin>>a>>b){
        while(b!=0){
            int x = a%b;
            a = b;
            b = x;
        }
        cout<<a<<endl;
    }
    return 0;
}

发表于 2020-03-03 17:03:40 回复(0)

小陈也只是想要一个实习罢了

//辗转相除法
#include<iostream>
using namespace std;
int zdgy(int a,int b){
    while(a%b!=0){
        a=a-a/b*b;
        int temp=a;
        a=b;
        b=temp;
    }
    return b;
}
int main(){
    int m,n;
    while(cin>>m>>n){
        if(m>n)
            cout<<zdgy(m,n)<<endl;
        else
            cout<<zdgy(n,m)<<endl;
    }
    return 0;
}

发表于 2020-01-13 11:06:54 回复(0)

C/C++

口阿这

//辗转相除法

#include <iostream>

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

发表于 2019-07-21 13:00:07 回复(0)

算法小屁孩

#include<bits/stdc++.h>
int max(int m,int n){
    if(n==0)
        return m;
    else
        return max(n,m%n);
}
int main(){
    int m,n;
    while(scanf("%d %d",&m,&n)!=EOF)
        printf("%d\n",max(m,n));
    return 0;
}//欧几里得算法的递归形式
------------------------------------------------------------------------------
#include<bits/stdc++.h>
int main(){
    int m,n,t;
    while(scanf("%d %d",&m,&n)!=EOF){
        while(n!=0){
            t=m%n;
            m=n;
            n=t;
        }
        printf("%d\n",m);
    }
    return 0;
}//欧几里得算法的非递归形式

编辑于 2019-03-04 13:30:04 回复(0)

C/C++

Train-wu

#include <iostream>

using namespace std;

class Integer {
private:
int _num;
public:
//构造函数
Integer(int num) {
  _num = num;
}
//计算当前Integer 和 b之间的最大公约数
int gcd(Integer b) {
  while (b._num != 0) {
   int temp = _num % b._num;
   _num = b._num; b._num = temp;
  }
  return _num;
}
};
int main() {
int a, b;
while (cin >> a >> b) {
  Integer A(a);
  Integer B(b);
  cout << A.gcd(B) << endl;
}
system("pause");
return 0;
}

发表于 2019-02-26 21:49:29 回复(0)

C/C++

秋招顺利offer多多

#include<iostream>
using namespace std;
int main(){
    int a,b;
    while(cin>>a>>b){
        int result=1;
        for(int i=2;i<=a&&i<=b;i++){
            if(a%i==0&&b%i==0){
                result*=i;
                a=a/i;
                b=b/i;
                i=2;
            }
        }
        cout<<result<<endl;
    }
    return 0;
}

发表于 2018-09-27 21:31:39 回复(0)

CompulsiveMan

#include<iostream>
using namespace std;

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }
int main(){
    int a,b;
    while(cin>>a>>b)cout << gcd(a, b) << endl;
    return 0;
}

短小的我嘻嘻

发表于 2018-03-28 16:54:38 回复(0)

Benson666

import java.util.Scanner;
public class Main{
    public static int gcd(int a, int b){
        if(b==0)
            return a;
        return gcd(b, a%b);
    }
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            System.out.println(gcd(in.nextInt(), in.nextInt()));
        }
    }
}

发表于 2018-02-26 14:31:34 回复(0)