Случай сбоя программы слишком большого значения MAX

Я использую сито из эратосфена, и он работает нормально. Но если я увеличу значение MAX до 50000, произойдет сбой приложения с необработанным исключением win32. Я думаю, что это произошло из-за переполнения стека.

Теперь мой вопрос: как мне это предотвратить?

#define MAX 50000
void Sieb_des_Eratosthenes()
{
    char Zahlen[MAX + 1] = {0};
    int i, j, x;

    for(i = 2; i <= MAX; i++)
    {
       if(Zahlen[i] == 0)     
       {
           Zahlen[i] = 1;
           for(j = i * i; j <= MAX; j += i)
           {
                 Zahlen[j] = -1;
           }      
       }
    }
}

Моя идея состояла в том, чтобы выделить память, но это не работает

#define MAX 50000
int Sieb_des_Eratosthenes()
{
    int i, j, x;
    char *array;
    array = malloc((MAX + 1) * sizeof(*array));
    if (array==NULL) {
       printf("Error allocating memory!\n");
       return -1; //return with failure
    }

    for(i = 2; i <= MAX; i++)
    {
       if(array[i] == 0)     
       {
           array[i] = 1;
           for(j = i * i; j <= MAX; j += i)
           {
                 array[j] = -1;
           }      
       }
    }
}
Источник

3 ответа

Решение

В то время как все остальные ответы верны. фактическая причина (целочисленное переполнение), вы просто пропустили некоторые детали реализации, предоставленные псевдокодом в вики. Следующие работы:

  • использование calloc выделить память. Затем все значения инициализируются 0 что значит true в смысле вики-псевдокода.
  • Во внешнем цикле только цикл до sqrt(MAX) см. псевдокод в статье вики.
  • Во внутреннем цикле отметьте все кратные i с 1 (false в смысле вики-псевдо-кода).
for(i = 2; i <= sqrt(MAX); i++) {
   if(array[i] == 0) { // "true"
       for(j = i*i; j <= MAX; j += i) {
             array[j] = 1;  // "false"
       }      
   }
}
  • Тогда все элементы, которые еще 0 простые числа.

Кроме того, нет необходимости использовать (подписано) int - все числа положительные, поэтому вы должны использовать unsigned int,

При таком подходе вы сможете использовать весь спектр unsigned int для MAX значение (до 4294967295 если unsigned int 32 бит)

Источник

Первоначальная проблема в вашей функции сбоя заключается в цикле for.

for(j = i * i; j <= MAX; j += i)

когда я становлюсь равным или большим, чем 46349 результат i * i переполняется и J получает значение -2146737495 а затем не удается в Zahlen[j] = -1;

Источник

int может содержать максимум от -2^31 до 2 ^ 31: http://en.wikipedia.org/wiki/Integer_(computer_science)

ваш переполнен инт

Источник
Другие вопросы по тегам