Как я могу зарезервировать память для очень большого сита?

Question

Я хочу генерировать простые числа, просеивая до 100 000 000, но объявление массива bool этого диапазона приводит к сбою моей программы. Это мой код:

long long i,j,n; 
bool prime[100000000+1]; 
prime[1]=prime[0]=false; 
for(i=2;i<=100000000;i++){ 
    prime[i]=true; 
} 
for(i=2;i<=100000000;i++){ 
    if(prime[i]==false){ 
     continue; 
    } 
    for(j=i*2;j<=100000000;j+=i){ 
     prime[j]=false; 
    } 
} 

Как я могу решить эту проблему?

Answer 1

Переменные могут храниться в трех разных областях памяти: статическая память, автоматическая память, динамическая память. Автоматическая память (нестатические локальные переменные) имеет ограниченный размер, вы пересекли ее, и это разбило программу. Альтернативой является отметка вашего массива static, который поместит ваш массив в статическое хранилище или использует динамическую память.

Поскольку это помечено C++ ... Используйте std::vector, который прост в использовании и использует динамическую память.

#include <vector> 
//... 
//... 
long long i,j,n; 
std::vector<bool> prime(100000000+1, true); 
prime[1]=prime[0]=false; 
for(i=2;i<=100000000;i++){ 
    if(prime[i]==false){ 
     continue; 
    } 
    for(j=i*2;j<=100000000;j+=i){ 
     prime[j]=false; 
    } 
} 

std::vector<bool> использует «битную эффективный» представление, что означает, что станд :: вектор здесь будет принимать около восьми раза меньше памяти, чем традиционный массив.

std::bitset аналогичен, но является постоянным по размеру, и вы должны пометить его как статичный, чтобы не занимать место в автоматической памяти.

Вы не спросили, но Erastostenes Sieve - не самый быстрый алгоритм для вычисления большого количества простых чисел. Кажется, что Sieve of Atkin быстрее и использует меньше памяти.

- Когда ваша система имеет 8-разрядные байты.

Answer 2

Размер массива prime 100 МБ и объявление такого большого массива в стеке недопустимо. Попробуйте поместить массив в глобальную область, чтобы выделить его в куче, или, альтернативно, выделить его с помощью нового (в C++) или malloc (в C). Не забывайте освобождать память после этого!

Answer 3

Вы должны не сделать одно монолитное сито такого размера. Вместо этого используйте сегментированное сито из Eratosthenes для просеивания в последовательных сегментах. В первом сегменте вычисляется наименьшее кратное из каждого просеивания просеивания, которое находится внутри сегмента, а затем кратность просеивающих прокладок помечены как составные в обычном порядке; когда все просеивающие простые числа использовались, оставшийся немаркированный номер в сегменте является простым. Затем для следующего сегмента наименьшее кратное каждого просеивающего прайма представляет собой кратное, которое закончило просеивание в предыдущем сегменте, и поэтому просеивание продолжается до завершения.

Рассмотрим пример просеивания от 100 до 200 в сегментах 20; 5 просеивающих простых чисел 3, 5, 7, 11 и 13. В первом сегменте от 100 до 120 биткрай имеет 10 слотов, а слот 0 соответствует 101, слот k, соответствующий 100 + 2 * k * + 1 и слот 9, соответствующий 119. Наименьший кратный 3 в сегменте равен 105, соответствующий слоту 2; слоты 2 + 3 = 5 и 5 + 3 = 8 также кратные 3. Наименьшее кратное 5 равно 105 в слоте 2, а слот 2 + 5 = 7 также кратно 5. Наименьшее кратное 7 равно 105 в слоте 2, а слот 2 + 7 = 9 также кратен 7. И так далее.

Функция primes принимает аргументы Lo, привет и дельта; ло и привет должен быть ровным, с Ио < приветом и л должен быть больше, чем квадратный корень из привета. Размер сегмента равен delta. Массив ps длины m содержит просеивающие пробы меньше квадратного корня от hi, с 2 удаленными, так как четные числа игнорируются, рассчитанные нормальным ситом Эратосфена. Массив qs содержит смещение в сито bitarray наименьшего кратного в текущем сегменте соответствующего просеивающего пресса. После каждого сегмента, ло успехи в два раза дельта, так что число, соответствующее индексу я из сита BitArray является ло + 2 я + 1.

function primes(lo, hi, delta) 
    sieve := makeArray(0..delta-1) 
    ps := tail(primes(sqrt(hi))) 
    m := length(ps) 
    qs := makeArray(0..m-1) 
    for i from 0 to m-1 
    qs[i] := (-1/2 * (lo + ps[i] + 1)) % ps[i] 
    while lo < hi 
    for i from 0 to delta-1 
     sieve[i] := True 
    for i from 0 to m-1 
     for j from qs[i] to delta step ps[i] 
     sieve[j] := False 
     qs[i] := (qs[i] - delta) % ps[i] 
    for i from 0 to delta-1 
     t := lo + 2*i + 1 
     if sieve[i] and t < hi 
     output t 
    lo := lo + 2*delta 

Для приведенный выше образец, это называется primes(100, 200, 10). В приведенном выше примере qs первоначально [2,2,2,10,8], соответствующий наименьшим кратным 105, 105, 105, 121 и 117, и сбрасывается для второго сегмента в [1,2,6, 0,11], соответствующие наименьшим кратным 123, 125, 133, 121 и 143.

Значение delta имеет критическое значение; вы должны сделать delta настолько большим, насколько это возможно, так долго на нем вписывается в кэш-память, для скорости. Используйте библиотеку своего языка для bitarray, так что вы берете только один бит для каждого места сита. Если вам нужен простой Решето Эратосфена для расчета просеивания простых чисел, это моя любимая:

function primes(n) 
    sieve := makeArray(2..n, True) 
    for p from 2 to n step 1 
    if sieve(p) 
     output p 
     for i from p * p to n step p 
      sieve[i] := False 

Вы можете увидеть больше алгоритмов с простыми числами в my blog.