Но надо бы оформить поаккуратней.
У числа
есть делители, не имеющие пары: 1,
, все остальные делители - парные:
, где
. То есть, у
самое большее
делителя. (здесь и далее говоря "делитель", я подразумеваю, делитель, меньший
). На самом деле, равенство достигается только для
, в общем случае делителей гораздо меньше.
Во всяком случае, получаем
. При
это выражение не меньше 6, для
можем убедиться, посчитав явно.
Если
, то непарный делитель только единица, а пары собираются из
. В общем, тут
.
И тогда
, и правая часть превысит 6 опять же при
.
Таким образом, при
мы можем гарантировать, что
. Ну и поскольку единица - всегда делитель, то
и число на экране всегда уменьшается (уже независимо от
- проблемы возникнут только при
, но это тривиальный случай).
Если в какой-то момент встретится простое, то все, мы победили. Если нет, то пока оно больше 15, беспокоиться не о чем, продолжаем такой обратный отсчет.
Допустим, на экране показалось составное число, меньшее 16. Из вышесказанного следует, что это число из набора
. Их можно перебрать "руками" и получить, что нечетное простое в самом деле получается:
P.S. На самом деле, что любопытно - их этого списка видно, что на экране должно появиться не вообще нечетное простое, а простое, больше 3. Вообще, если ретроспективно посмотреть на соотношения выше, то возникают сомнения, что числа, большие миллиона таким образом спустятся хотя бы до трехзначных простых... Надо бы программку составить. А может и в OEIS такая последовательность уже есть?