Областная олимпиада по математике, 2007 год, 11 класс

Чудаковатый математик написал книгу, страницы которой пронумерованы от 2 до 400 и читать которую следует так: сначала находим последнюю страницу (400-ю) и читаем страницы (по возрастанию) с номерами, которые имеют общие делители > 1 с 400. Затем берем последнюю из непрочитанных страниц и повторяем то же самое, то есть уже читаем страницы с номерами, имеющими общий делитель >1 с 399. Далее процесс повторяется с последней непрочитанной страницей и так далее. Итак, последовательно нами будут прочитаны страницы с номерами: 2, 4, 5, $\dots$, 400, 3, 7, 9, $\dots$, 399, $\dots$. Какая страница будет прочитана последней?

Комментарий/решение

Запишем все простые числа до 37: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37. Страницы 2 и 5 будут прочитаны вместе со страницей 400; 3, 7 и 19 вместе с 399; 11 и 31 вместе с 341; 13 и 29 вместе с 377; 17 и 23 вместе с 391. Страница 37 могла быть прочитана вместе со страницами 74, 111, 148, 185, 222, 259, 296, 333, 370, но все они будут прочитаны раньше вместе со страницами 2, 3, 5 и 7.

Ответ:37