Программа Php для подсчета простых чисел в диапазонах

Учитывая диапазон [L, R], нам нужно найти общее количество простых чисел в диапазоне [L, R], где 0 <= L <= R < 10000. Учтите, что существует большое количество запросов для разные диапазоны.
Примеры:

Input : Query 1 : L = 1, R = 10
        Query 2 : L = 5, R = 10
Output : 4
         2
Explanation
Primes in the range L = 1 to R = 10 are 
{2, 3, 5, 7}. Therefore for query, answer 
is 4 {2, 3, 5, 7}.
For the second query, answer is 2 {5, 7}.

Простое решение — сделать следующее для каждого запроса [L, R]. Перейдите от L к R, проверьте, является ли текущее число простым. Если да, увеличьте количество. Наконец, верните счет.
Эффективным решением является использование Решета Эратосфена, чтобы найти все простые числа до заданного предела. Затем мы вычисляем массив префиксов для хранения счетчиков до каждого значения до предела. Когда у нас есть массив префиксов, мы можем отвечать на запросы за время O(1). Нам просто нужно вернуть префикс [R] — префикс [L-1].

Выход:

2
4

Пожалуйста, обратитесь к полной статье о подсчете простых чисел в диапазонах для получения более подробной информации!