Прихлоп: Есть, капитан Тёрнер. У этого корабля снова выверен курс. Но там, где мы будем… ей места нет. Один день на берегу. Десять лет в море. Не слишком ли дорогая цена?
Уилл: Это смотря какой день.
Ни для кого не секрет, что сейчас Уилл Тёрнер — капитан Летучего Голландца.
В далёком 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