Почему ошибка сегментации (ядро сбрасывается)?

Question

Я учу C. Для школьного задания я написал код для печати простых чисел в определенном диапазоне. Я использую 50000 как maxbyte для бит-массива. Мой код компилируется, но он дает мне ошибку, называемую «segmentation fault: 11» (она останавливается на 46337). Может кто-нибудь сказать мне, что проблема в моем коде? Как я могу исправить эту ошибку? Спасибо.

#include <stdio.h> 
#include <stdlib.h> 

//#define MAXBYTES 1000000 
#define MAXBYTES 50000 


void setBit(unsigned int A[], int k); 
unsigned getBit(unsigned int A[], int k); 
void print_prime (int prime_num); 
void sieve_Prime(unsigned int bit_arr[]); 

int main (int argc, char** argv) 
{ 
    //int bit_arr[MAXBYTES];  //This is the bit array (32 X MAXBYTES) 
    unsigned int bit_arr[MAXBYTES];  //or bit_arr[MAXBYTES] 
    int i; 

    for (i=0; i < MAXBYTES; i++) 
    { 
     bit_arr[i] = 0x00;   //initialize all bits to 0s 
    } 

    setBit(bit_arr, 0);    //0 is not prime, set it to be 1 
    setBit(bit_arr, 1);    //1 is not prime, set it to be 1 

    sieve_Prime(bit_arr); 
    printf("\n"); 

    return 0; 

} 

//Set the bit at the k-th position to 1 
void setBit(unsigned int A[], int k) 
{ 
    int i = k/32; 
    int pos = k % 32; 

    unsigned int flag = 1;  //flag = 0000 ..... 00001 
    flag = flag << pos;   //flag = 0000...010...000 (shifted k positions) 

    A[i] = A[i] | flag;   //Set the bit at the k-th position in A[i]; 
} 

//get the bit at the k-th position 
unsigned getBit(unsigned int A[], int k) 
{ 
    int i =k/32; 
    int pos = k % 32; 

    unsigned int flag = 1; 

    flag = flag << pos; 

    if (A[i] & flag) 
     return 1; 
    else 
     return 0; 
} 


void print_prime (int prime_num) 
{ 
    //print a prime number in next of 8 columns 
    static int numfound=0; 

    if (numfound % 8 == 0) 
     printf("\n"); 
    if (prime_num+1 < MAXBYTES*8)      
     printf("%d\t", prime_num); 
    numfound++; 
} 

void sieve_Prime(unsigned int bit_arr[]) 
{ 
    int i; 
    int k; 

    int next_prime = 2; 

    print_prime(2); 

    while (next_prime+1 < MAXBYTES*8)     
    { 
     k = next_prime; 

     //multiples of next_prime is not primpe 
     while(next_prime*k < MAXBYTES*8)     
     { 
      setBit(bit_arr, next_prime*k);  //set it to be 1 
      k++;  
     } 

     //find next_prime by skipping non-prime bits marked 1 
     next_prime++; 
     while (next_prime + 1 < MAXBYTES*8 && getBit(bit_arr, next_prime)) 
     { 
      next_prime++; 
     } 
     print_prime(next_prime); 

    } 
} 

Answer 1

В while(next_prime*k < MAXBYTES*8)

Наибольшее значение для next_prime*k является (MAXBYTES*8-1)*(MAXBYTES*8-1). Это большое значение не может быть сохранено в подписанном int и может превратиться в отрицательное значение, вызывающее segfault.

Использование

while(unsigned(next_prime*k) < MAXBYTES*8) 

устранит Segfault.

Answer 2

Первое, что нужно сделать, это задуматься о том, что на самом деле означает MAXBYTES. Поскольку вы выделяете массив bit_arr, чтобы иметь столько int, а не байтов, вы выделяете в 4 раза больше необходимой вам памяти и просто теряете ее. Кроме того, вы назначаете его как локальный в стеке - многие машины не будут иметь столько места в стеке, что, вероятно, является причиной неудачи с большим числом. Лучше либо сделать его статическим, либо выделить его в кучу с malloc().

Кроме того, вам нужно больше заботиться о диапазонах чисел, используемых: i и k, например, может быть до MAXBYTES*8, так что вы, возможно, придется сделать их long, если увеличить его. И у вас есть промежуточный результат k * next_prime, который может переполнять равнину int.

Лично, так как вы индексировать массив по битам, я установил бы свои пределы в тех же условиях, чтобы сделать вещи яснее - есть MAXBITS, выделить массив в качестве MAXBITS/32, сравните пределы и диапазоны в терминах битов, и убедитесь, что ваш бит подсчитан вписывается в типы переменных.