ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1940. Непростые годы

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Прихлоп: Есть, капитан Тёрнер. У этого корабля снова выверен курс. Но там, где мы будем… ей места нет. Один день на берегу. Десять лет в море. Не слишком ли дорогая цена?
Уилл: Это смотря какой день.
Ни для кого не секрет, что сейчас Уилл Тёрнер — капитан Летучего Голландца. В далёком A-м году ему пришлось заключить договор с богиней Калипсо, согласно которому Уилл немедленно отправился в вечное плавание и сможет сойти на берег только через B лет после отплытия. Более того, договор не позволяет Уиллу более дня находиться на суше — он обязан будет вновь пуститься в плавание на очередные B лет.
Сегодняшний день очень важен для Уилла, ведь это очередная годовщина начала его плавания. С момента заключения договора он ещё ни разу не выходил на сушу. Чтобы немного развлечь себя, каждый год в этот самый день Уилл, отрываясь от своих многочисленных забот, выделяет k минут на кажущееся бесполезным со стороны занятие — проверку того, является ли номер текущего года простым числом. Но Уилл видит в этом особый смысл — по легенде, в конце года с простым номером богиня Калипсо может отменить один из заключённых ранее с ней договоров. Капитан Летучего Голландца умеет проверять число на простоту лишь одним способом: последовательно делить его на все натуральные числа подряд, начиная с двойки и заканчивая числом, на единицу меньшим проверяемого. Поскольку Уилл не силён в математике и что-либо считает лишь раз в год, то для того, чтобы разделить одно число на другое, ему требуется целая минута. Если за k минут делитель номера года не найден, то Уилл бросает подсчёты и считает его простым. А в конце такого года он тешит себя надеждами, что именно сейчас богиня Калипсо явится к нему с радостными вестями. Так сколько же всего лет будут простыми по мнению Уилла в период с первой годовщины отплытия и до года, когда он в первый раз сможет выйти на берег, включительно, если богиня не сжалится над пиратом?

Исходные данные

В единственной строке через пробел записаны целые числа A, B и k (2 ≤ A, B ≤ 109; 1 ≤ k ≤ 300).

Результат

Выведите единственное целое число — количество лет в указанном периоде, имеющих простой номер, по мнению Уилла.

Пример

исходные данныерезультат
23 7 3
2

Замечания

Уилл посчитает года 25 и 29 простыми, а 24, 26, 27, 28 и 30 — нет.
Автор задачи: Ксения Карпова (подготовка — Егор Щелконогов)
Источник задачи: Открытый командный чемпионат УрФУ по программированию — 2012