Approach for problem

[everule1]

Sum of divisors of all numbers less than n in less than O(n) time

It’s just \sum_{i=1}^n i\lfloor n/i\rfloor Since i divides \lfloor n/i \rfloor values less than n. To optimise this we can notice that \lfloor n/i\rfloor goes through only O(\sqrt{n}) values. n/j is i for j\in (\lfloor n/(i+1) \rfloor, \lfloor n/i \rfloor \ ] My code