compute_totient.rs

// Totient function for
// all numbers smaller than
// or equal to n.

// Computes and prints
// totient of all numbers
// smaller than or equal to n

use std::vec;

pub fn compute_totient(n: i32) -> vec::Vec<i32> {
    let mut phi: Vec<i32> = Vec::new();

    // initialize phi[i] = i
    for i in 0..=n {
        phi.push(i);
    }

    // Compute other Phi values
    for p in 2..=n {
        // If phi[p] is not computed already,
        // then number p is prime
        if phi[(p) as usize] == p {
            // Phi of a prime number p is
            // always equal to p-1.
            phi[(p) as usize] = p - 1;

            // Update phi values of all
            // multiples of p
            for i in ((2 * p)..=n).step_by(p as usize) {
                phi[(i) as usize] = (phi[i as usize] / p) * (p - 1);
            }
        }
    }

    phi[1..].to_vec()
}

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

    #[test]
    fn test_1() {
        assert_eq!(
            compute_totient(12),
            vec![1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4]
        );
    }

    #[test]
    fn test_2() {
        assert_eq!(compute_totient(7), vec![1, 1, 2, 2, 4, 2, 6]);
    }

    #[test]
    fn test_3() {
        assert_eq!(compute_totient(4), vec![1, 1, 2, 2]);
    }
}