Number of common factors

Math Enumeration Number Theory

79.9% acceptance

Feb 25, 2026

680

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn common_factors(a: i32, b: i32) -> i32 {
    let g = Self::gcd(a, b);
    (1..=g).filter(|&x| g % x == 0).count() as i32
  }

  fn gcd(a: i32, b: i32) -> i32 {
    if b == 0 { a } else { Self::gcd(b, a % b) }
  }
}