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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Common Factors

Number: 2507

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given two positive integers a and b, return the number of common factors of a and b. A common factor is an integer x that divides both a and b.

Key Insights

  • The common factors of a and b are exactly the divisors of their greatest common divisor (gcd).
  • Compute the gcd of a and b; every divisor of the gcd is a common factor.
  • Iterate through numbers from 1 to √(gcd) to count factors, taking care to count both factors when i is not the square root.

Space and Time Complexity

Time Complexity: O(√g) where g is the gcd of a and b. Space Complexity: O(1)

Solution

The solution involves two main steps:

  1. Compute the greatest common divisor (gcd) of a and b using the Euclidean algorithm.
  2. Count all divisors of the gcd by iterating from 1 to √(gcd). For every number i that divides the gcd, count i and, if i is not the square root, also count gcd/i as another distinct factor. This method efficiently finds all common factors.

Key data structures used include basic integer variables for computation. The Euclidean algorithm efficiently finds the gcd, and iteration with a loop is used to count the factors.

Code Solutions

import math

def commonFactors(a, b):
    # Compute the greatest common divisor of a and b
    g = math.gcd(a, b)
    count = 0
    # Iterate through potential factors from 1 to sqrt(g)
    i = 1
    while i * i <= g:
        if g % i == 0:
            count += 1  # i is a factor
            # If i is not the square root, count the paired factor g // i
            if i != g // i:
                count += 1
        i += 1
    return count

# Example usage:
print(commonFactors(12, 6))  # Expected output: 4
← Back to All Questions