Ctrl K

Самая тесная пара простых

Средняя
Даны два целых числа low и high. Среди простых чисел отрезка [low, high] (концы включены) найдите два, p < q, у которых разность q - p минимальна. Верните [p, q]. Если таких пар с минимальной разностью несколько, выберите пару с наименьшим p. Если в отрезке меньше двух простых, верните [-1, -1].
Пример 1
low=20, high=40 → [29, 31]

Простые в отрезке: 23, 29, 31, 37. Самый маленький промежуток — 2, между 29 и 31.

Пример 2
low=2, high=7 → [2, 3]

Пара 2 и 3 отличается всего на 1 — меньше не бывает.

Пример 3
low=24, high=28 → [-1, -1]

Простых чисел в отрезке нет вовсе.

Ограничения
  • 1 ≤ low ≤ high ≤ 3 · 10⁶
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиПростые числа до границы СредняяЛазер в зеркальной комнате СредняяПервое простое-палиндром СредняяN-е число, кратное одному из трёх СредняяНесократимые дроби до знаменателя Средняя
загружаем Python…
Вход
low=20, high=40
Ожидается
[29, 31]

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 98 тестов на сервере, включая скрытые.