题目

牛客网 - 最大公约数

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

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

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

示例

输入
49 14
输出
7

思路

思路一 - 穷举法

一个约数同时被两个数可以整除，此时如果两个数一大一小，最大约数肯定小于或等于那个小的数，穷举即可

Java 写法：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            System.out.println(gcd(a, b));
        }
    }
    
    public static int gcd(int a, int b) {
        int small = a < b ? a : b;
        int _gcd = 1;
        for (int i = 2; i <= small; i++) {
            if (a % i == 0 && b % i == 0) {
                _gcd = i;
            }
        }
        return _gcd;
    }
}

Python 写法：

def solv(a, b):
    small = a if a < b else b
    _gcd = 1
    for i in range(2, small + 1):
        if a % i == 0 and b % i == 0:
            _gcd = i
    return _gcd


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

思路二 - 辗转相除法

欧几里得算法，即 gcd(a, b) = gcd(a, a mod b)，详解如下：

• 对 gcd(a, b)，当 a mod b = 0，则最大公约数为 b
• 对 gcd(a, b)，当 a mod b != 0，则令 a = b，b = a mod b，递归求解

Java 写法：

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

Python 写法：

def solv(a, b):
    if a % b == 0:
        return b
    return solv(b, a % b)


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

总结

近几天熟悉 py 的语法，也学习学习这些简单的数学题