We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Common Factors

Difficulty: Easy

Problem 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.

Key Insights

  • Common factors of two numbers can be determined by finding the divisors of their greatest common divisor (GCD).
  • The GCD can be computed efficiently using the Euclidean algorithm.
  • The number of divisors of a number can be calculated by iterating up to its square root and checking for divisibility.

Space and Time Complexity

Time Complexity: O(sqrt(gcd(a, b)))
Space Complexity: O(1)

Solution

To solve this problem, we will:

  1. Calculate the GCD of the two numbers a and b using the Euclidean algorithm.
  2. Determine the number of divisors of the GCD by iterating from 1 to the square root of the GCD, checking for divisibility.
  3. Count each divisor and its complement (i.e., gcd / i) to account for pairs of divisors.

Code Solutions

def commonFactors(a: int, b: int) -> int:
    def gcd(x, y):
        while y:
            x, y = y, x % y
        return x
    
    gcd_value = gcd(a, b)
    count = 0
    
    # Count divisors of gcd_value
    for i in range(1, int(gcd_value**0.5) + 1):
        if gcd_value % i == 0:
            count += 1  # i is a divisor
            if i != gcd_value // i:
                count += 1  # gcd_value / i is also a divisor
    
    return count
← Back to All Questions