Factorial Trailing Zeros in Arbitrary Base

lib.rs

use std::collections::HashMap;

fn prime_factors(number: i32) -> HashMap<i32, i32> {
    let mut prime_factors: HashMap<i32, i32> = HashMap::new();
    let mut candidate_factor = 2;
    let mut n = number;

    while n > 1 {
        while n % candidate_factor == 0 {
            if let Some(count) = prime_factors.get_mut(&candidate_factor) {
                *count += 1;
            } else {
                prime_factors.insert(candidate_factor, 1);
            }
            n /= candidate_factor;
        }
        candidate_factor += 1;
    }
    prime_factors
}

fn zeroes(base: i32, number: i32) -> i32 {
    let base_decomp = prime_factors(base);

    base_decomp
        .into_iter()
        .map(|(factor, exponent)| {
            let mut sum = 0;
            let mut i = 1;

            loop {
                let result = number / factor.pow(i);
                sum += result;
                if result == 0 {
                    break;
                };
                i += 1;
            }

            sum / exponent
        })
        .min()
        .unwrap()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn basic_cases() {
        assert_eq!(zeroes(10, 10), 2);
        assert_eq!(zeroes(16, 16), 3);
    }
}