当前位置：首页 > article >正文

【创作赢红包】求最大公因数与最小公倍数

article 2025/1/8 4:41:07

什么是最小公因数

最大公约数（Greatest Common Divisor）指两个或多个整数共有约数中最大的一个。也称最大公因数、最大公因子，a， b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。

辗转相除法求最小公因数

用(a，b)表示a和b的最大公因数：有结论(a，b)=(a，ka+b)，其中a、b、k都为自然数。

也就是说，两个数的最大公约数，将其中一个数加到另一个数上，得到的新数，其公约数不变，比如(4，6)=(4+6，6)=(4，6+2×4)=2.

要证明这个原理很容易：如果p是a和ka+b的公约数，p整除a，也能整除ka+b.那么就必定要整除b，所以p又是a和b的公约数，从而证明他们的最大公约数也是相等的.

基于上面的原理，就能实现我们的迭代相减法：(78，14)=(64，14)=(50，14)=(36，14)=(22，14)=(8，14)=(8，6)=(2，6)=(2，4)=(2，2)=(0，2)=2

基本上思路就是大数减去小数，一直减到能算出来为止，在作为练习的时候，往往进行到某一步就已经可以看出得值.

迭代相减法简单，不过步数比较多，实际上我们可以看到，在上面的过程中，由(78，14)到(8，14)完全可以一步到位，因为(78，14)=(14×5+8，14)=(8，14)，由此就诞生出我们的辗转相除法.

即：(a， b) = (a % b， b) = （b, a %b）

相当于每一步都把数字进行缩小，等式右边就是每一步对应的缩小结果。

对（a， b）连续使用辗转相除，直到小括号内右边数字为0，小括号内左边的数就是两数最大公约数。

代码实现

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        while(T --> 0){
            int a = scan.nextInt();
            int b = scan.nextInt();
            System.out.println(gcd(a,b));
        }
    }
    public static int gcd(int a,int b){
        return b!=0 ? gcd(b,a%b):a;
    }
}

最小公倍数

与最大公因数类似，只是把约数换成了倍数

求最小公倍数

十分简单，我们只需知道简单的一个定理，两个数的最小公倍数就等于两个数的乘积/他们的最大公因数

即 a * b / gcd(a,b)；

例题

小张是软件项目经理，他带领 33 个开发组。

工期紧，今天都在加班呢。

为鼓舞士气，小张打算给每个组发一袋核桃（据传言能补脑）。

他的要求是：

各组的核桃数量必须相同
各组内必须能平分核桃（当然是不能打碎的）
尽量提供满足 1,21,2 条件的最小数量（节约闹革命嘛）

输入格式

包含 a,b,c 三个正整数，表示每个组正在加班的人数。

输出格式

一个正整数，表示每袋核桃的数量。

数据范围

0<a,b,c<30

输入样例1：

2 4 5

输出样例1：

输入样例2：

3 1 1

输出样例2：

代码实现

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        int c = scan.nextInt();
        int a_b = a * b / gcd(a,b);
        int a_b_c =a_b * c / gcd(a_b,c);
        System.out.println(a_b_c);
    }
    public static int gcd(int a,int b){
        return b != 0 ? gcd(b , a % b) : a;
    }
}