Все задачи
Легко Решено: 0 Процент решений: 0%

Количество простых чисел на отрезке

Посчитайте, сколько простых чисел лежит между двумя границами включительно.

Чему вы научитесь

  • Отмечать составные числа с помощью решета
  • Считать отмеченные значения внутри отрезка
  • Обрабатывать пустые отрезки и числа 0 и 1

Условие

Сколько простых чисел от 1 до 100? А от 50 до 60? Посчитайте простые p, для которых low ≤ p ≤ high. Не забудьте, что 0 и 1 простыми не являются. Решето до high быстро даёт ответ.

Реализуйте count_primes_in_range(low, high).

Входные данные

low: нижняя граница (включительно).

high: верхняя граница (включительно).

Выходные данные

Верните количество простых чисел на отрезке. Если low > high, отрезок пуст и ответ равен 0.

Ограничения

0 ≤ low ≤ 1 000 000

0 ≤ high ≤ 1 000 000

Примеры

Пример 1
Ввод:
low = 1
high = 100

Ожидаемый вывод:
expected = 25
Ввод:
long long low = 1;
long long high = 100;

Ожидаемый вывод:
long long expected = 25;
Ввод:
long low = 1;
long high = 100;

Ожидаемый вывод:
long expected = 25;

Пояснение

До 100 всего 25 простых чисел (2, 3, 5, … 97), поэтому ответ 25.

Пример 2
Ввод:
low = 50
high = 60

Ожидаемый вывод:
expected = 2
Ввод:
long long low = 50;
long long high = 60;

Ожидаемый вывод:
long long expected = 2;
Ввод:
long low = 50;
long high = 60;

Ожидаемый вывод:
long expected = 2;

Пояснение

Между 50 и 60 простые только 53 и 59, поэтому ответ 2.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Постройте решето до high, вычёркивая кратные каждого простого числа начиная с его квадрата.

Подсказка 2

Затем посчитайте числа от low до high, которые остались отмеченными как простые.

Подсказка 3

Если low больше high, ничего вычислять не нужно.

Ожидаемая сложность

время O(high log log high), доп. память O(high)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.