Skip to content

2427. Number of Common Factors

Description

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

Solutions

Solution 1: Enumeration

Thinking

Every common factor divides \(g=\gcd(a,b)\). With \(a,b\le 1000\), test each integer in \([1,g]\) against \(g\); there is no need to test \(a\) and \(b\) separately.

We can first calculate the greatest common divisor \(g\) of \(a\) and \(b\), then enumerate each number in \([1,..g]\), check whether it is a factor of \(g\), if it is, then increment the answer by one.

The time complexity is \(O(\min(a, b))\), and the space complexity is \(O(1)\).

1
2
3
4
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))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func commonFactors(a int, b int) (ans int) {
    g := gcd(a, b)
    for x := 1; x <= g; x++ {
        if g%x == 0 {
            ans++
        }
    }
    return
}

func gcd(a int, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function commonFactors(a: number, b: number): number {
    const g = gcd(a, b);
    let ans = 0;
    for (let x = 1; x <= g; ++x) {
        if (g % x === 0) {
            ++ans;
        }
    }
    return ans;
}

function gcd(a: number, b: number): number {
    return b === 0 ? a : gcd(b, a % b);
}

Solution 2: Optimized Enumeration

Thinking

Method 1 already scans up to \(g\). Factors come in pairs, so enumerate to \(\sqrt{g}\) and count both \(x\) and \(g/x\) (once when they coincide), in \(O(\sqrt{g})\).

Similar to Solution 1, we can first calculate the greatest common divisor \(g\) of \(a\) and \(b\), then enumerate all factors of the greatest common divisor \(g\), and accumulate the answer.

The time complexity is \(O(\sqrt{\min(a, b)})\), and the space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def commonFactors(self, a: int, b: int) -> int:
        g = gcd(a, b)
        ans, x = 0, 1
        while x * x <= g:
            if g % x == 0:
                ans += 1
                ans += x * x < g
            x += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int commonFactors(int a, int b) {
        int g = gcd(a, b);
        int ans = 0;
        for (int x = 1; x * x <= g; ++x) {
            if (g % x == 0) {
                ++ans;
                if (x * x < g) {
                    ++ans;
                }
            }
        }
        return ans;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int commonFactors(int a, int b) {
        int g = gcd(a, b);
        int ans = 0;
        for (int x = 1; x * x <= g; ++x) {
            if (g % x == 0) {
                ans++;
                ans += x * x < g;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func commonFactors(a int, b int) (ans int) {
    g := gcd(a, b)
    for x := 1; x*x <= g; x++ {
        if g%x == 0 {
            ans++
            if x*x < g {
                ans++
            }
        }
    }
    return
}

func gcd(a int, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function commonFactors(a: number, b: number): number {
    const g = gcd(a, b);
    let ans = 0;
    for (let x = 1; x * x <= g; ++x) {
        if (g % x === 0) {
            ++ans;
            if (x * x < g) {
                ++ans;
            }
        }
    }
    return ans;
}

function gcd(a: number, b: number): number {
    return b === 0 ? a : gcd(b, a % b);
}

Comments