Easy

题目描述

给你两个正整数 a 和 b，返回 a 和 b 的公因数的数目。

如果 x 可以同时整除 a 和 b，则认为 x 是 a 和 b 的一个公因数。

示例 1：

输入：a = 12, b = 6
输出：4
解释：12 和 6 的公因数是 1、2、3、6 。

示例 2：

输入：a = 25, b = 30
输出：2
解释：25 和 30 的公因数是 1、5 。

提示：

  • 1 <= a, b <= 1000

解题思路

解题思路

这道题要求找出两个数的所有公因数的个数。我们可以从以下几个角度来思考：

方法一：暴力枚举（推荐）

最直接的方法是遍历从 1 到 min(a, b) 的所有数字，检查每个数字是否能同时整除 a 和 b。由于公因数不可能大于两个数中的较小者，所以只需要遍历到 min(a, b) 即可。

方法二：基于最大公约数优化

我们知道两个数的所有公因数都是它们最大公约数（GCD）的因数。因此可以先求出 GCD，然后找 GCD 的所有因数。这种方法在 a 和 b 较大时会更高效，但由于题目限制 a, b ≤ 1000，暴力方法已经足够快。

实现细节

  • 遍历范围是 [1, min(a, b)]
  • 对于每个候选数 i，检查 a % i == 0 && b % i == 0
  • 统计满足条件的数字个数

由于数据范围较小（≤1000），暴力枚举是最简单且高效的解法。

代码实现

class Solution {
public:
    int commonFactors(int a, int b) {
        int count = 0;
        int minVal = min(a, b);
        for (int i = 1; i <= minVal; i++) {
            if (a % i == 0 && b % i == 0) {
                count++;
            }
        }
        return count;
    }
};

class Solution:
    def commonFactors(self, a: int, b: int) -> int:
        count = 0
        min_val = min(a, b)
        for i in range(1, min_val + 1):
            if a % i == 0 and b % i == 0:
                count += 1
        return count

public class Solution {
    public int CommonFactors(int a, int b) {
        int count = 0;
        int minVal = Math.Min(a, b);
        for (int i = 1; i <= minVal; i++) {
            if (a % i == 0 && b % i == 0) {
                count++;
            }
        }
        return count;
    }
}

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var commonFactors = function(a, b) {
    let count = 0;
    let min = Math.min(a, b);
    
    for (let i = 1; i <= min; i++) {
        if (a % i === 0 && b % i === 0) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(min(a, b))需要遍历从 1 到 min(a, b) 的所有数字
空间复杂度O(1)只使用了常数个额外变量

相关题目