# Go4Fun - Functional programming and more # Rust Interview Puzzles: Find common factors

### Problem

Given two positive integer numbers `a` and `b`, we need to find their common factors. A common factor of `a` and `b` is an integer number that divides both `a` and `b` without a remainder.

#### Examples:

 Input `a` Input `b` Output `18` `6` `[1, 2, 3, 6]` `5` `10` `[1, 5]` `3` `5` `` `252` `105` `[1, 3, 7, 21]`

### Solution

``````fn find_common_factors(a: u32, b: u32) -> Vec<u32> {
assert!(a > 0 && b > 0, "a & b must be positive");

fn gcd(mut a: u32, mut b: u32) -> u32 {
while a != b {
if a > b {
a = a - b;
} else {
b = b - a;
}
}
a
}

(1..=gcd(a, b))
.filter(|n| a % n == 0 && b % n == 0)
.collect()
}
``````

### Explanation

We iterate over `[1..gcd(a, b)]` numbers and `filter` in only numbers `n` that divide both `a` and `b` without a remainder (`a % n == 0 && b % n == 0`). It is enough to iterate up to the Greatest common divisor returned by the `gcd(a, b)` function call.

And to calculate the `gcd` we use the simple Euclidean algorithm.

### Complexity

The time complexity of the solution is `O(gcd(a, b))`. The auxiliary space complexity is `O(1)`.

Rust Playground with this code