Вопрос Пс помогите программу сделать

[sasha286]

Дано число n. Найдите число из диапазона от 1 до n с максимальной суммой своих делителей (включая непростые делители, 1 и само число). Если таких чисел несколько, выведите минимальное из них.
На вход программе подается натуральное n <= 1 000 000. Выведите искомое число.

Дайте алгоритм спс

 

[samaramax]

#include unsigned long Sum(unsigned long a, unsigned long i) { return a == i? 1 : (Sum(a, i + 1) + ((a % i) ? 0 : i)); } int main() { unsigned long n, i, max, a, buf; scanf("%lu", &n); max = a = 0; for(i = 1; i <= n; i++) if ((buf = Sum(i, 1)) > max) { max = buf; a = i; } printf("%lu ", a); return 0; }

 

[ololoid]

М-м-м... Ну, можно тупенько двойной цикл замутить, но если n=1000000, то он будет выполняться десятки миллиардов раз - несколько обременительно. Нужен жесткий матан, какая-то теорема о делителях. Математик нужен. Вот до чего допедрил мой Core i7 за минуту: 240240 999936 Дальше все туже и туже. Вот еще: 393120 1693440 Ну и на закуску 480480 2032128 Все, вырубаю, батарейку экономить надо.