dsalgo/
sum_of_multiples_table_with_multiples_fast_zeta.rs

1use crate::sieve_of_eratosthenes_enumerate_primes_usize::enumerate_primes;
2
3/// O(N\log{\log{N}})
4
5pub fn sum_of_multiples(size: usize) -> Vec<usize> {
6    let mut f: Vec<_> = (0..size).collect();
7
8    for p in enumerate_primes(size) {
9        for i in (1..(size - 1) / p + 1).rev() {
10            f[i] += f[i * p];
11        }
12    }
13
14    f
15}
16
17#[cfg(test)]
18
19mod tests {
20
21    use super::*;
22
23    #[test]
24
25    fn test() {
26        let f = sum_of_multiples(10);
27
28        assert_eq!(f, [0, 45, 20, 18, 12, 5, 6, 7, 8, 9]);
29    }
30}