The Number of Common Factors problem asks you to count the number of integers that are factors of both a and b. An integer x is a common factor if it divides both a and b without remainder. This Number of Common Factors coding problem is a clean number theory exercise involving GCD and factor enumeration.
Microsoft, Meta, Amazon, and Google ask this easy problem to test number theory fundamentals — specifically, understanding that the common factors of a and b are exactly the factors of gcd(a, b). The math, number theory, and enumeration interview pattern is demonstrated here with a clean GCD insight.
GCD + factor enumeration. Compute g = gcd(a, b). Then count the divisors of g by iterating from 1 to sqrt(g). For each i that divides g, count both i and g/i (if they're different). This reduces an O(min(a,b)) scan to O(sqrt(gcd(a,b))).
a=12, b=8. gcd(12,8)=4. Divisors of 4: 1, 2, 4. Count = 3. Verify: 1 divides both ✓, 2 divides both ✓, 4 divides both ✓, 3 divides 12 but not 8 ✗.
a=25, b=30. gcd=5. Divisors of 5: 1, 5. Count = 2.
Common factors equal divisors of GCD — this is the key number theory insight. Memorize: "count common factors of a and b" = "count divisors of gcd(a,b)". Divisor counting with a sqrt loop is O(sqrt(n)). Practice both GCD computation and divisor counting as building blocks — they combine frequently in number theory interview problems at Google, Meta, and Microsoft.
