Простое число больше 6 миллионов

Question

Я решал вопрос в Hackerrank, и вопрос заключался в том, чтобы найти количество простых чисел в диапазоне. Поскольку при использовании обычной методологии ожидался тайм-аут, я использовал Сито Эратосфена. Большинство тестов работали, за исключением двух скрытых тестов. Я запустил код в компиляторе GDB и выяснил, что код поддерживает только значения до 6 миллионов. Что мне делать? Код приведен ниже:

#include<cstring>
#include<cstdio>
#include <iostream>
#include <algorithm>
using namespace std;


void SieveOfEratosthenes(unsigned long long int a,unsigned long long int b) 
{ 
    unsigned long long int count=0; 
    bool prime[b+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (unsigned long long int p=2; p*p<=b; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            for (unsigned long long int i=p*p; i<=b; i += p) 
                prime[i] = false; 
        } 
    } 
  
    for (unsigned long long int p=a; p<b; p++) 
       if (prime[p] &&p!=1) 
           count++;
    cout<<count;
          
} 
  
int main() 
{ 
    unsigned long long int a,b;
    cin>>a>>b;
    SieveOfEratosthenes(a,b); 
    return 0; 
} 

Answer 1

Вы создаете в своей функции массив bool, который будет храниться в стеке. На Windows типичный максимальный размер стека составляет 1 МБ, тогда как на типичном современном Linux он составляет 8 МБ. Вы создаете массив с 6 миллионами записей, который будет около 6 МБ.

Для решения этой проблемы вы можете создать vector вместо массива, который будет сохранен в куче.

Answer 2

Похоже на классное c переполнение стека. bool prime[b+1]; выделяется в стеке, и вы достигли предела.

Если это работает на Linux, то максимально допустимый размер стека обычно составляет около 8 МБ или меньше, так что есть хороший шанс, что вы только что превысили это значение.

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