我要招人

去企业版

首页 > 试题广场 >

最大公约数

[编程题]最大公约数

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

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

输入描述:

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

输出描述:

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

示例1

输入

49 14

输出

算法知识视频讲解

Java

WIT_221

import java.util.Scanner;

// 数学思想: 辗转相除法 (当然也可以直接从1开始暴力循环

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int nums1,nums2;

nums1 = in.nextInt();

nums2 = in.nextInt();

while(nums1%nums2 != 0){

int res = nums1 % nums2;

nums1 = nums2;

nums2 = res;

}

System.out.print(nums2);

}

发表于 2024-03-17 10:53:33 回复(0)

Java

LHC0512

Java 解法简单粗暴

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int i = scanner.nextInt();
        int j = scanner.nextInt();
        int res=1;
        for (int k = 1; k < Math.min(i, j); k++) {
            if (i%k==0&&j%k==0)
                res=Math.max(res,k);
        }
        System.out.println(res);
    }
}

发表于 2020-03-06 10:42:02 回复(0)

Java

♪Hippo

import java.util.Arrays;
import java.util.Scanner;

public class Main
{
    public static void main(String... as)
    {
        Scanner sc = new Scanner(System.in);

        while (sc.hasNextInt())
            System.out.println(gcd(sc.nextInt(), sc.nextInt()));
        sc.close();
    }
    private static int gcd(int a, int b)
    {
        return b == 0 ? a : gcd(b, a % b);
    }
    
}

发表于 2018-09-19 16:22:08 回复(0)

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)

Java

电科渣硕

//简单点，如果求余为0.则为公约数，直到求出最大的公约数。
//从复杂度明显不如辗转相除法。因为一开始并不知道这个算法。
import java.util.Scanner;
public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int s=0;
        for(int i=1; i <= a&&i <= b; i++)
        {
            if(a%i==0 && b%i==0)
            {
                s=i;
            }
        }
        System.out.println(s);
    }
}

编辑于 2018-05-27 10:57:22 回复(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)