На уроке астрономии Лосяш рассказал Крошу о загадочном «Решете Эратосфена». Крош решил, что это идеальный план для постройки новой межзвёздной трассы от Земли до далёкой Морковной туманности. Трасса будет проходит вдоль прямой линии, размеченной в световых годах.
Крош решил установить автоматические заправочные станции в тех точках, чьё расстояние от Земли выражается простым числом.
Для начала строительства Крош выбрал участок пути от отметки A до отметки B (включительно) и расставил там станции.
Чтобы станции не улетели в открытый космос, их нужно соединить между собой силовыми тросами.
Условия монтажа суровые:
- Каждая станция должна быть закреплена хотя бы одним тросом (то есть к каждой точке должна вести хотя бы одна линия).
- Энергопотребление силовых тросов огромно, поэтому их суммарная длина должна быть минимально возможной.
- Первая станция должна быть соединяться с пунктом
A, а последняя с пунктом B
- Если на отрезке
[A;B] нет простых чисел, то надо соединить пункт A с пунктом B
|
Задача:
Помогите Крошу рассчитать минимальную суммарную длину силовых тросов для строительства отрезка [A;B]
|
Входные данные
Координаты пунктов А и В (0 < A < B < 1_000_000)
Выходные данные
Ответ на задачу - минимальная суммарная длина силовых тросов |
Примеры
| Входные данные |
Ожидаемый результат |
Пояснения |
| 24 28 |
4 |
на отрезке [24 ; 28] нет простых чисел,
соединаем границы отрезка |
| |
|
|
|