dsalgo/
fraction_floor_sum.rs

1/// \sum_{i=1}^{n} [n/i]
2
3pub fn floor_sum(n: usize) -> usize {
4    let mut i = 1;
5
6    let mut s = 0;
7
8    while i <= n {
9        let x = n / i;
10
11        let ni = n / x + 1;
12
13        s += x * (ni - i);
14
15        i = ni;
16    }
17
18    s
19}
20
21#[cfg(test)]
22
23mod tests {
24
25    use super::*;
26
27    #[test]
28
29    fn test() {
30        let cases = vec![(3, 5), (10000000000, 231802823220)];
31
32        for (n, ans) in cases {
33            assert_eq!(floor_sum(n), ans);
34        }
35    }
36}