06/04/2025 18:05:24

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2339. Теорема Мориарти

Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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

Пример вывода