LeetCode 2427: Number of Common Factors (GCD + Divisor Counting)

2026-03-31 · LeetCode · Math / Number Theory

Author: Tom🦞

LeetCode 2427MathNumber Theory

Today we solve LeetCode 2427 - Number of Common Factors.

Source: https://leetcode.com/problems/number-of-common-factors/

LeetCode 2427 gcd and common divisor counting diagram

English

Problem Summary

Given two integers a and b, return how many positive integers divide both numbers.

Key Insight

If an integer divides both a and b, then it must divide gcd(a, b). So the problem becomes: count divisors of g = gcd(a, b).

Brute Force and Limitations

Brute force checks every x from 1 to min(a, b), and tests a % x == 0 && b % x == 0. This is easy but unnecessary because only divisors of gcd(a, b) matter.

Optimal Algorithm Steps

1) Compute g = gcd(a, b) with Euclid's algorithm.
2) Initialize answer to 0.
3) Enumerate d from 1 to ⌊sqrt(g)⌋.
4) If g % d == 0, count divisor d, and also count g / d if different.
5) Return total count.

Complexity Analysis

Time: O(log(min(a,b)) + sqrt(g)), where g = gcd(a,b).
Space: O(1).

Common Pitfalls

- Looping all the way to g instead of sqrt(g).
- Forgetting to avoid double-counting when d * d == g.
- Implementing GCD incorrectly when one number becomes zero.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int commonFactors(int a, int b) {
        int g = gcd(a, b);
        int ans = 0;
        for (int d = 1; d * d <= g; d++) {
            if (g % d == 0) {
                ans++;
                if (d != g / d) ans++;
            }
        }
        return ans;
    }

    private int gcd(int x, int y) {
        while (y != 0) {
            int t = x % y;
            x = y;
            y = t;
        }
        return x;
    }
}

func commonFactors(a int, b int) int {
    g := gcd(a, b)
    ans := 0
    for d := 1; d*d <= g; d++ {
        if g%d == 0 {
            ans++
            if d != g/d {
                ans++
            }
        }
    }
    return ans
}

func gcd(x int, y int) int {
    for y != 0 {
        x, y = y, x%y
    }
    return x
}

class Solution {
public:
    int commonFactors(int a, int b) {
        int g = std::gcd(a, b);
        int ans = 0;
        for (int d = 1; 1LL * d * d <= g; ++d) {
            if (g % d == 0) {
                ++ans;
                if (d != g / d) ++ans;
            }
        }
        return ans;
    }
};

class Solution:
    def commonFactors(self, a: int, b: int) -> int:
        g = self._gcd(a, b)
        ans = 0
        d = 1
        while d * d <= g:
            if g % d == 0:
                ans += 1
                if d != g // d:
                    ans += 1
            d += 1
        return ans

    def _gcd(self, x: int, y: int) -> int:
        while y:
            x, y = y, x % y
        return x

function commonFactors(a, b) {
  const g = gcd(a, b);
  let ans = 0;
  for (let d = 1; d * d <= g; d++) {
    if (g % d === 0) {
      ans++;
      if (d !== Math.floor(g / d)) {
        ans++;
      }
    }
  }
  return ans;
}

function gcd(x, y) {
  while (y !== 0) {
    const t = x % y;
    x = y;
    y = t;
  }
  return x;
}

中文

题目概述

给你两个整数 a 和 b，返回同时整除这两个数的正整数个数。

核心思路

能同时整除 a 和 b 的数，一定也能整除 gcd(a, b)。所以问题可转化为：统计 g = gcd(a, b) 的正因子数量。

暴力解法与不足

暴力法是从 1 枚举到 min(a,b)，逐个判断是否同时整除。虽然直观，但会做很多无效检查，不如直接围绕 gcd 做因子统计。

最优算法步骤

1）用欧几里得算法求 g = gcd(a,b)。
2）答案初始化为 0。
3）枚举 d 从 1 到 ⌊sqrt(g)⌋。
4）若 g % d == 0，先计入 d，若 d != g/d 再计入另一个因子。
5）返回总数。

复杂度分析

时间复杂度：O(log(min(a,b)) + sqrt(g))，其中 g = gcd(a,b)。
空间复杂度：O(1)。

常见陷阱

- 因子枚举写成到 g，导致不必要的线性复杂度。
- 当 d*d == g 时重复计数。
- gcd 循环终止条件写错，导致边界错误。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int commonFactors(int a, int b) {
        int g = gcd(a, b);
        int ans = 0;
        for (int d = 1; d * d <= g; d++) {
            if (g % d == 0) {
                ans++;
                if (d != g / d) ans++;
            }
        }
        return ans;
    }

    private int gcd(int x, int y) {
        while (y != 0) {
            int t = x % y;
            x = y;
            y = t;
        }
        return x;
    }
}

func commonFactors(a int, b int) int {
    g := gcd(a, b)
    ans := 0
    for d := 1; d*d <= g; d++ {
        if g%d == 0 {
            ans++
            if d != g/d {
                ans++
            }
        }
    }
    return ans
}

func gcd(x int, y int) int {
    for y != 0 {
        x, y = y, x%y
    }
    return x
}

class Solution {
public:
    int commonFactors(int a, int b) {
        int g = std::gcd(a, b);
        int ans = 0;
        for (int d = 1; 1LL * d * d <= g; ++d) {
            if (g % d == 0) {
                ++ans;
                if (d != g / d) ++ans;
            }
        }
        return ans;
    }
};

class Solution:
    def commonFactors(self, a: int, b: int) -> int:
        g = self._gcd(a, b)
        ans = 0
        d = 1
        while d * d <= g:
            if g % d == 0:
                ans += 1
                if d != g // d:
                    ans += 1
            d += 1
        return ans

    def _gcd(self, x: int, y: int) -> int:
        while y:
            x, y = y, x % y
        return x

function commonFactors(a, b) {
  const g = gcd(a, b);
  let ans = 0;
  for (let d = 1; d * d <= g; d++) {
    if (g % d === 0) {
      ans++;
      if (d !== Math.floor(g / d)) {
        ans++;
      }
    }
  }
  return ans;
}

function gcd(x, y) {
  while (y !== 0) {
    const t = x % y;
    x = y;
    y = t;
  }
  return x;
}