dsalgo/
mobius_function.rs

1use crate::prime_factorize_trial_division::prime_factorize;
2
3// TODO: use faster factorization algorithm.
4pub fn mobius_function(n: u64) -> i8 {
5    assert!(n > 0);
6
7    if n == 1 {
8        return 1;
9    }
10
11    let mut u = 1;
12
13    for (_, e) in prime_factorize(n) {
14        if e > 1 {
15            return 0;
16        }
17
18        u *= -1;
19    }
20
21    u
22}
23
24#[cfg(test)]
25
26mod tests {
27
28    #[test]
29
30    fn test() {
31        use super::*;
32
33        assert_eq!(mobius_function(1), 1);
34
35        assert_eq!(mobius_function(2), -1);
36
37        assert_eq!(mobius_function(4), 0);
38    }
39}