Для вычисления количества простых чисел в определённом числовом диапазоне можно использовать решето Эратосфена. 15

Алгоритм работает следующим образом: 1

1. Создать список чисел от 2 до заданного предела N. 1
2. Определить первое число в списке (в начале это будет 2) и удалить все его кратные, кроме самого числа. 1
3. Перейти к следующему числу в списке и повторить предыдущий шаг. 1
4. Продолжать процесс, пока не дойдём до конца списка. 1 По завершении алгоритма все оставшиеся числа в списке будут простыми. 1

Ещё один способ — использовать массив префиксов. 2 Для этого нужно вычислить количество простых чисел до каждого значения до заданного предела с помощью решета Эратосфена. 2 Затем для вычисления количества простых чисел в заданном диапазоне нужно вернуть значение префикса для конечного значения диапазона за вычетом префикса для начального значения диапазона. 2

Также для нахождения простых чисел в заданном диапазоне можно использовать решето Сундарама или решето Аткина. 1