1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

const L: usize = 10000001;
let mut c = vec![false; L];
let mut tb = vec![0; L];
let mut cb = vec![0; L]; 
tb[1] = 1;
let mut pb = Vec::with_capacity(664579);
for i in 2..L {
    if !c[i] {
        pb.push(i);
        tb[i] = i + 1;
        cb[i] = 1;
    }
    for &p in &pb {
        if i * p >= L {
            break;
        }
        c[i * p] = true;
        if i % p == 0 {
            let cnt = cb[i];
            let non_f = i / p.pow(cnt);
            tb[i * p] = tb[non_f] * (p.pow(cnt + 2) - 1) / (p - 1); 
            cb[i * p] = cb[i] + 1;
            break;
        } else {
            tb[i * p] = tb[i] * tb[p];
            cb[i * p] = 1;
        }
    }
}