Стандартным улучшением, которое следует применить, будет обработка каждого i-го бита как числа 2*i+1, представляющего, таким образом, только шансы , сокращая размер массивав половине.Это также повлечет за собой, для каждого нового простого числа p, начиная разметку с p*p и увеличивая на 2*p, пропуск пропусков.2 сам по себе особый случай.См. Также этот вопрос с множеством ответов.
Другая стратегия заключается в переключении на сегментированное сито .Таким образом, вам нужно только около pi(sqrt(m)) = 2*sqrt(m)/log(m) памяти (m - ваш верхний предел), выделенной для начальной последовательности простых чисел, с которой вы бы просеивали меньший массив фиксированного размера, последовательно представляя сегменты чисел.Если вам нужны только простые числа в некотором узком дальнем диапазоне [m-d,m], вы сразу перейдете к просеиванию этого диапазона после того, как собраны все необходимые простые числа, как показано, например, в этого ответа .
Согласно вашим особенностям, чтобы получить простые числа до 10 ^ 9, работа с одним непрерывным массивом все еще возможна.Используя bitarray только для шансов , вам потребуется 10 ^ 9/16 байт, т.е. около 60 МБ памяти.Проще работать по сегментам;нам нужно только 3402 простых числа, ниже 31627, чтобы просеять каждый сегментный массив ниже 10 ^ 9.