Сумма делителей, не равных самому числу

[rockclimber]

wrest в сообщении #1331406 писал(а):

Верной дорогой идёте, товарищ! Я вот пошел туда же прям сразу ;)
Решето тут лучше всего, просто надо помнить, что если просеял первые $10^6$ натурльных чисел, то надежно отсеялись только неприкасаемые числа до $10^3$

Именно об этом я и говорю. Для проверки первых $N$ чисел вы перебираете $(N-1)^2$ вариантов, а я предлагаю способ, как число вариантов немного (а может быть, и много) сократить.

[Dmitriy40]

rockclimber
Я тоже сомневаюсь в сокращении вариантов, там же все взаимные перемножения надо учитывать, а это число растёт как факториал, пусть даже от корня, что явно быстрее квадрата.
Попробуйте подсчитать для того же 52 сколько всего вариантов сочетаний надо проверить, у меня без учёта произведений разных простых уже получается 120 вариантов. И думаю полное количество будет сильно больше 2700 (считать лень).

[rockclimber]

Dmitriy40 в сообщении #1331420 писал(а):

Попробуйте подсчитать для того же 52 сколько всего вариантов сочетаний надо проверить, у меня без учёта произведений разных простых уже получается 120 вариантов.

Спасибо, что посчитали
Эти 120 вариантов закрывают не число 52, а все числа от 1 до 52. Потому что для всех чисел меньше 52 надо проверять все те же самые комбинации!
Там получается следующее: простые числа - 2, 3, 5, 7. Их степени соответственно (максимальные): 4, 4, 2, 2. С учетом того, что степень каждого изменяется от 0 до максимальной, общее число вариантов будет порядка $5 \cdot 5 \cdot 3 \cdot 3 = 225$. Примерно в 10 раз меньше, чем у wrest.

[wrest]

rockclimber в сообщении #1331399 писал(а):

Вы хотели сказать "много кода писать руками"?

И это тоже :) Мы тут параллельно тестируем числа на кубичность в соседнией теме, на скорость. Много вложенных циклов замедляет программу же, при каждом начале цикла: в стек все положил, из стека все достал, мусор собрал... и т.д. и т.п.