返回目录

最大公约数：也称最大公约数，最大公因子，是指两个或多个整数共有约数中最大的一个

1）示例1：
输入：16 24 输出：8
2）示例2：
输入：24 45 输出：3
3）示例3：
输入：36 24 48 输出：12

Python源码

def prime_factors(n):
    factors = []
    i = 2
    while n > 1:
        if n % i == 0:
            factors.append(i)
            n //= i
        else:
            i += 1
    return factors

def gcd(a, b):
    factors_a = prime_factors(a)
    factors_b = prime_factors(b)

    i = j = 0
    ret = 1
    while i < len(factors_a) and j < len(factors_b):
        if factors_a[i] == factors_b[j]:
            ret *= factors_a[i]
            i += 1
            j += 1
        elif factors_a[i] < factors_b[j]:
            i += 1
        else:
            j += 1
    return ret

def main():
    a, b = map(int, input().split())
    ret = gcd(a, b)
    print(f"{a}和{b}的最大公因数是：{ret}")

if __name__ == "__main__":
    main()

C语言源码

#include<stdio.h>

// 函数用于找到一个数的质因数并将它们存储在数组中
void fun(int * arr, int n)
{
    int i = 2, j = 0;
    while (n > 1)
    {
        if (n % i == 0)
        {
            arr[j++] = i; // 存储质因数
            n /= i;       // 将n除以质因数
        }
        else 
        {
            i++;          // 移动到下一个数字
        }
    }
}

// 函数用于找到两个数的最大公因数（GCD）
int gcd(int a, int b) 
{
    // 用于存储a和b的质因数的数组
    int arr_a[100] = {0}; // 存储a的质因数
    int arr_b[100] = {0}; // 存储b的质因数
  
    // 找到a和b的质因数
    fun(arr_a, a);
    fun(arr_b, b);

    // 找到公共的质因数并将它们相乘
    int i = 0, j = 0, ret = 1;
    while (arr_a[i] != 0 && arr_b[j] != 0) 
    {
        if (arr_a[i] == arr_b[j]) 
        {
            ret *= arr_a[i]; // 相乘得到公共因数
            i++;
            j++;
        }
        else if (arr_a[i] > arr_b[j])
        {
            j++;
        }
        else
        {
            i++;
        }
    }
    return ret;
}

int main() 
{
    int a = 0;
    int b = 0;
    scanf("%d %d", &a, &b);
    int ret = gcd(a, b); // 找到最大公因数
    printf("%d和%d的最大公因数是：%d", a, b, ret);
    return 0;
}

Java源码

import java.util.Scanner;

public class GCDBySubtractionAlgorithm {

    // 使用更相减损法（辗转相减法）求最大公约数
    public static int gcd(int a, int b) {
        while (a != b) {
            if (a > b)
                a -= b;
            else
                b -= a;
        }
        return a;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入两个整数：");
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        scanner.close();

        int ret = gcd(a, b);
        System.out.printf("最大公约数是：%d%n", ret);
    }
}