Сколько простых чисел от 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
Примеры
Ввод:
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.
Ввод:
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. Следуйте условию и ограничениям выше.