Монетки

Применим алгоритм, похожий на решето Эратосфена. Возьмем последовательность ai = i2 + 1: 2, 5, 10, 17, 26, 37, 50, 65, ...

Возьмем первое число — 2 = 12 + 1. Посмотрим, какие числа на него делятся (для них все 2 – это ответ) — это числа (1 + 2·0)2 + 1, (1 + 2·1)2 + 1, (1 + 2·2)2 + 1, .... Поделим все эти числа на 2 (на максимальную степень двойки, на которую они делятся), получим обновленную последовательность: 1, 5, 5, 17, 13, 37, 25, 65, ...

Теперь возьмем следующее число – 5 = 22 + 1. Посмотрим, какие числа делятся на него — это (1 + 5·0)2 + 1, (1 + 5·1)2 + 1, (1 + 5·2)2 + 1, ... Поделим их все на 5 (тоже на максимальную степень 5, на которую они делятся): 1, 1, 5, 17, 13, 37, 1, 65, ...

Теперь возьмем третье число — 5, опять проделаем ту же самую операцию, получим: 1, 1, 1, 17, 13, 37, 1, 13, ...

Несложно доказать, что каждый очередной делитель (1, 5, 5, ...), который мы берем — простое число или 1. Таким образом, мы находим все простые делители чисел вида n2 + 1.

Алгоритм работает за O(n + n / 2 + n / 3 + ... + n / n), что равно