Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2339. Теорема Мориарти
Простые числа, разложение на множителиОлимпиадные задачи на русском языке
| 02/04/2017 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 4) |
Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Изощренный ум профессора Мориарти проявил себя не только в организации преступлений,
но и в решении математических проблем. Наибольшую известность получили его монографии
"Трактат о биноме" и "Планетная динамика". Также он вел переписку со многими математиками.
В номере гостиницы в Мейрингеме было найдено неоконченное письмо, адресованное Каталану.
В нем Мориарти писал "Существует бесконечно много таких простых `p`, что и `p+2` - тоже простое.
Я обнаружил поистине чудесное доказательство этого, но смогу записать его полностью только
после неотложной встречи". В номер он уже не вернулся.
Только в 2013 математик Чжан Итан сумел доказать, что существует бесконечное количество
пар простых чисел на расстоянии менее `7*10^7`. К настоящему времени эту оценку
расстояния удалось уменьшить до 246.
Напишите программу, подсчитывающую количество пар простых
чисел `(p_i,\ p_j)`, таких что `A\ ≤\ p_i\ <\ p_j\ \ ≤\ B` и `p_j-p_i\ ≤\ D`.
Формат ввода
Первая строка ввода содержит три целых числа – `A,\ B` (`1\ ≤\ A\ <\ B\ ≤\ 10^{14}`, `B-A\ ≤\ 10^7`)
и `D` (`2\ ≤\ D\ ≤\ 10^7`).
Формат вывода
Вывести одно целое число – количество пар простых чисел на расстоянии не
более `D` в диапазоне от `A` до `B`.
Пример ввода
1 10 2
Пример вывода
3
