Кстати, можно подсчитать эту самую сумму для всех чисел от 1 до n за линейную сложность.
Надо использовать
модифицированное решето Эратосфена, чтобы найти для каждого числа его минимальный простой делитель. Используя эти данные можно для каждого числа найти его минимальный простой делитель в максимальной степени, на которую число делится - один множитель из разложения на простые множители.
Далее, используя эти данные, можно подсчитать сумму всех простых делителей используя формулу
S=(p1^(k1+1)-1)/(1-p1)*...*(pm^(km+1)-1)/(1-pm) (тут
p1^k1...pm^km - разложение числа на простые множители).
Надо считать эту сумму делителей от меньших чисел к большим (обозначим ее S(n)). Тогда S(n) = S(n/p^k)*(p^k*p-1)/(p-1).
Но это так, для любопытных. Я думаю в вашей задаче достаточно для кадого числа проверять все делители до корня (а оставшиеся делители получаются как n/i, если i - делитель до корня). Надо только аккуратно разобрать случай, когда
i = sqrt(n) - тогда второй делитель не надо рассматривать, ибо это вторая копия того же самого.
