Как кодировать для сегментированного сита, учитывая два интервала?

Question

Я ясно понял Сито Эратосфена. Но я сталкиваюсь с трудностями в понимании сегментированного сита. Мой вопрос заключается в том, что с учетом двух диапазонов

(a=b=10^8) 

как найти простые числа между этими двумя интервалами, где

b-a<=10^5)

Пожалуйста, помогите мне разработать код.

Answer 1

Проверьте эту ссылку для реализации C ++ и объяснения сегментированного сита для одного диапазона n https://www.geeksforgeeks.org/segmented-sieve/

Для вашего случая, когда у вас есть диапазон от a до b с верхним пределом 10 ^ 8 вашего максимумаразмер сегмента будет sqrt (10 ^ 8) = 10000, а если верхний предел разности ba равен 10 ^ 5, вы будете иметь максимум 10 сегментов для обработки.

Возьмите алгоритм по данной ссылке и используйтеваш диапазон b в качестве входных данных n и вычисление простого вектора базового вектора, затем отрегулируйте пределы

 // Divide the range [0..n-1] in different segments 
// We have chosen segment size as sqrt(n). 
int low = limit; 
int high = 2*limit; 

, установив низкое значение на ближайший кратный предел, равный <= a, и проигнорируйте любой результат в выходных данных <a </p>

Это должно решить вашу проблему в представленном виде.