Операции с ЦНЧ

[Ktina]

С ЦНЧ (Целым Неотрицательным Числом) разрешается производить следующие операции:
1) Умножать на составное число, 2) Прибавлять или отнимать простое число.

Докажите, что из нуля можно получить любое ЦНЧ не более чем за 3 операции, и найдите наименьшее ЦНЧ, которое нельзя получить из 0 не более чем за 2 операции.

[mihaild]

Простые числа получаются за один шаг, составные - не более чем за $3$: $0 \to 3 \to 1 \to 1 \cdot x$.
За $2$ операции гарантированно можно получить все (небольшие) четные (гипотеза Гольдбаха), все простые, все нечетные вида $p \pm 2$. Наименьшим числом не такого вида является $93 = 3 \cdot 31$. Его нельзя получить меньше чем за $3$ операции: последняя операция - это либо прибавление / вычитание простого (тогда перед ней у нас было составное число - либо четное, либо $91$ или $95$, а составные числа не получаются за $1$ шаг), либо умножение на составное - тогда перед ней было $1$, а $1$ тоже не получается за $1$ шаг.

[Ktina]

mihaild
Большое спасибо!
Бонусный вопрос (который следовало в самом начале задать): С олимпиады какого года эта задача?

[worm2]

Ну, видимо, 1993-го или конца 1992-го. Это хоть как-то её оправдывает.