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

Задача . ПР_13_011


Задача

Темы:
Задание 13 

Выпускник Родион заснул за чтением романа Ф. М. Достоевского «Преступление и наказание» перед экзаменом. Ему приснился настоящий ужастик: он сам превратился в Родиона Раскольникова, попал в душный, мрачный Петербург и проделал путь в 730 шагов до дома, где убил старуху-процентщицу и её сестру Лизавету. На столе в его крошечной каморке лежит мешок с монетами, украденными у старухи. Следователь застал Родиона за подсчётом монет и предложил избавиться от улик следующим способом:
  • Если текущее количество монет N — составное число, Раскольников может отдать часть монет вдове Мармеладова, оставив в мешке K штук. Порфирий Петрович разрешает выбрать в качестве K только собственный «больший делитель» числа N (такой делитель, что 1 < K < N и K² ≥ N).
  • Если текущее количество монет N — простое число, Родиона охватывает лихорадка, и он в панике выбрасывает в окно две, три, пять или семь монет.
  • Дело заканчивается, как только в мешке остаётся ровно 0 монет.
Сделав подсчёты, Родион получил ровно 730 способов и проснулся в «холодном поту».
Определите минимальное возможное количество монет, которое изначально могло лежать в мешке Раскольникова, чтобы количество способов было равно 730. В ответе укажите только число.
 

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