Олимпиадный тренинг

Задача . ПР_13_001 - Копия


Задача

Темы:
Выпускник Павел заснул за чтением поэмы Н. В. Гоголя «Мёртвые души» перед экзаменом. Ему приснился настоящий ужастик: он сам превратился в коллежского советника Павла Ивановича Чичикова, попал в губернский город NN и отправился скупать умерших крестьян. Увидев число душ в реестре, Чичиков понял, что Собакевич купится на следующую схему, и предложил заплатить ровно по одному рублю за каждый возможный вариант проведения сделки по следующим правилам:
  • Если текущее число душ N в списке — составное число, Собакевич может вычеркнуть часть, оставив в реестре K душ. Он разрешает выбрать в качестве K только собственный «больший делитель» числа N (такой делитель, что 1 < K < N и K² ≥ N).
  • Если текущее количество душ N — простое число, Чичиков из «уважения к хозяину» сам вычёркивает из списка две, три, пять или семь душ.
  • Сделка заканчивается, как только в реестре остаётся ровно 0 душ.
Сделав подсчёты, Собакевич получил ровно 200 способов проведения сделки, и в этот момент Павел проснулся в «холодном поту».
Определите минимальное возможное количество душ, которое изначально могло быть в реестре, если в результате этой схемы Чичиков заплатил бы Собакевичу ровно 200 рублей. В ответе укажите только число.
 

Статистика успешных решений по компиляторам