# Number of Common Factors
**Difficulty:** EASY
[External](https://leetcode.com/problems/number-of-common-factors)
Canonical: https://scaleengineer.com/dsa/problems/number-of-common-factors
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
---
## Problem
Given two positive integers `a` and `b`, return _the number of **common** factors of_ `a` _and_ `b`.

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

**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`

# Approaches
## Brute Force Iteration
This approach involves iterating through all possible candidates for a common factor and checking if they divide both `a` and `b`.
**Time:** O(min(a, b)) - The loop runs `min(a, b)` times, and each iteration involves constant time operations (modulo and comparison). · **Space:** O(1) - We only use a constant amount of extra space for variables like `count`, `limit`, and the loop counter `i`.
**Pros:** Very simple to understand and implement.; Requires no advanced mathematical knowledge.
**Cons:** Inefficient for large values of `a` and `b`, as the number of iterations is directly proportional to the smaller input number.
### Explanation
The simplest way to find common factors is to test every possible candidate. A number `x` can only be a common factor of `a` and `b` if it divides both. This implies that `x` cannot be larger than `a` and `x` cannot be larger than `b`. Therefore, any common factor must be less than or equal to `min(a, b)`. We can iterate through all integers `i` from 1 up to `min(a, b)`. For each `i`, we perform a check: `if (a % i == 0 && b % i == 0)`. If the condition is true, we've found a common factor and we increment a counter. After checking all numbers up to `min(a, b)`, the counter will hold the total number of common factors.

```java
class Solution {
    public int commonFactors(int a, int b) {
        int count = 0;
        int limit = Math.min(a, b);
        for (int i = 1; i <= limit; i++) {
            if (a % i == 0 && b % i == 0) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Determine the smaller of the two numbers, `limit = min(a, b)`.
- Loop through each integer `i` from 1 to `limit`.
- Inside the loop, check if `i` divides both `a` and `b` without a remainder (`a % i == 0 && b % i == 0`).
- If it does, increment the `count`.
- After the loop finishes, return `count`.

## Optimized Approach using GCD
This method leverages a key mathematical property: the set of common factors of two numbers, `a` and `b`, is identical to the set of factors of their Greatest Common Divisor (GCD). This reduces the problem to finding the number of factors of a single, smaller number, which can be done efficiently.
**Time:** O(sqrt(min(a, b))) - The Euclidean algorithm for GCD takes `O(log(min(a, b)))` time. The main work is counting factors of the GCD, `g`, which takes `O(sqrt(g))` time. Since `g <= min(a, b)`, the overall complexity is dominated by `O(sqrt(g))`, which is bounded by `O(sqrt(min(a, b)))`. · **Space:** O(1) - The iterative Euclidean algorithm uses constant space. The factor counting loop also uses constant extra space.
**Pros:** Significantly more efficient, with a time complexity related to the square root of the input values.; Scales well for larger numbers beyond the given constraints.
**Cons:** Slightly more complex due to the need to implement or use a GCD function.; Requires understanding of number theory concepts (GCD and its properties).
### Explanation
A more efficient method is based on the mathematical insight that any common divisor of `a` and `b` must also be a divisor of their Greatest Common Divisor (GCD). Conversely, any divisor of `gcd(a, b)` is a common divisor of `a` and `b`. Therefore, the problem is equivalent to finding the number of divisors of `gcd(a, b)`.

The algorithm proceeds in two steps:
1.  **Calculate GCD:** First, we find the GCD of `a` and `b`, let's call it `g`. The Euclidean algorithm is a highly efficient method for this.
2.  **Count Factors of GCD:** Next, we count the number of factors of `g`. A standard optimization for counting factors is to iterate only up to the square root of `g`. For each number `i` that divides `g`, we know that `g/i` is also a factor. If `i` is the square root of `g`, `i` and `g/i` are the same, so we count it once. Otherwise, we have found a pair of distinct factors (`i` and `g/i`), so we add two to our count.

```java
class Solution {
    // Helper function to compute GCD using Euclidean algorithm
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public int commonFactors(int a, int b) {
        int g = gcd(a, b);
        int count = 0;
        for (int i = 1; i * i <= g; i++) {
            if (g % i == 0) {
                // i is a factor, so g/i is also a factor.
                if (i * i == g) {
                    // If i is the square root, we count it once.
                    count++;
                } else {
                    // Otherwise, we count both i and g/i.
                    count += 2;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Calculate the Greatest Common Divisor (GCD) of `a` and `b`. Let this be `g`. An efficient way is using the Euclidean algorithm.
- Initialize a factor counter `count` to 0.
- Iterate with a loop variable `i` from 1 up to the integer part of the square root of `g`.
- For each `i`, check if `g % i == 0`.
- If it is, we have found factors:
    - If `i * i == g`, then `i` is the square root, and we have found one unique factor. Increment `count` by 1.
    - Otherwise, `i` and `g/i` are a pair of distinct factors. Increment `count` by 2.
- After the loop, return `count`.

# Solutions
### Java

```java
class Solution {
public
  int commonFactors(int a, int b) {
    int g = gcd(a, b);
    int ans = 0;
    for (int x = 1; x <= g; ++x) {
      if (g % x == 0) {
        ++ans;
      }
    }
    return ans;
  }
private
  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

```

### CPP

```cpp
class Solution {
public:
  int commonFactors(int a, int b) {
    int g = gcd(a, b);
    int ans = 0;
    for (int x = 1; x <= g; ++x) {
      ans += g % x == 0;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def commonFactors(self, a: int, b: int) -> int: g = gcd(a, b) return sum(g % x == 0 for x in range(1, g + 1))

```