problemeasyalgorithmsleetcode-2427leetcode 2427leetcode2427

Number of Common Factors

EasyUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

Given two positive integers a and b, return _the number ofcommon factors of _a andb.

An integer x is a common factor of a and b if x divides both a and b.

Examples

Example 1

Input: a = 12, b = 6
Output: 4
Explanation: The common factors of 12 and 6 are 1, 2, 3, 6.

Example 2

Input: a = 25, b = 30
Output: 2
Explanation: The common factors of 25 and 30 are 1, 5.

Constraints

  • 1 <= a, b <= 1000

Solution

Method 1 – Brute Force Enumeration

Intuition

The common factors of a and b are the divisors of gcd(a, b). Enumerate all numbers from 1 to min(a, b) and count those that divide both.

Approach

  1. For i from 1 to min(a, b), check if both a % i == 0 and b % i == 0.
  2. Count and return the total.

Code

C++
class Solution {
public:
    int commonFactors(int a, int b) {
        int cnt = 0;
        for (int i = 1; i <= min(a, b); ++i)
            if (a % i == 0 && b % i == 0) ++cnt;
        return cnt;
    }
};
Go
func commonFactors(a, b int) int {
    cnt := 0
    for i := 1; i <= a && i <= b; i++ {
        if a%i==0 && b%i==0 { cnt++ }
    }
    return cnt
}
Java
class Solution {
    public int commonFactors(int a, int b) {
        int cnt = 0;
        for (int i = 1; i <= Math.min(a, b); ++i)
            if (a % i == 0 && b % i == 0) cnt++;
        return cnt;
    }
}
Kotlin
class Solution {
    fun commonFactors(a: Int, b: Int): Int {
        var cnt = 0
        for (i in 1..minOf(a, b))
            if (a % i == 0 && b % i == 0) cnt++
        return cnt
    }
}
Python
class Solution:
    def commonFactors(self, a: int, b: int) -> int:
        return sum(a%i==0 and b%i==0 for i in range(1, min(a,b)+1))
Rust
impl Solution {
    pub fn common_factors(a: i32, b: i32) -> i32 {
        let mut cnt = 0;
        for i in 1..=a.min(b) {
            if a%i==0 && b%i==0 { cnt += 1; }
        }
        cnt
    }
}
TypeScript
function commonFactors(a: number, b: number): number {
    let cnt = 0;
    for (let i = 1; i <= Math.min(a, b); ++i)
        if (a % i === 0 && b % i === 0) cnt++;
    return cnt;
}

Complexity

  • ⏰ Time complexity: O(min(a, b))
  • 🧺 Space complexity: O(1)

Comments