1

我正在学习 C。对于学校作业，我编写了一些代码来打印一定范围内的素数。我使用 50000 作为位数组的最大字节。我的代码可以编译，但它给了我一个名为“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);

    }
}
4

2 回答 2

3

在while(next_prime*k < MAXBYTES*8)

的最大值next_prime*k为(MAXBYTES*8-1)*(MAXBYTES*8-1)。这个大值不能保存在有符号中int，可能会变成负值，导致段错误。

使用

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

将消除段错误。

于 2013-08-18T02:00:07.587 回答
2

首先要做的是下定决心了解MAXBYTES实际含义。由于您分配数组bit_arr以具有那么多整数，而不是字节，因此您分配了所需内存的 4 倍，只是浪费了它。此外，您将它分配为堆栈上的本地 - 许多机器在堆栈上不会有那么多空间，这可能是它失败并出现更大数字的原因。最好将其设为静态或使用malloc().

此外，您需要更加注意使用的数字的范围：例如i，k可能高达，因此如果增加它MAXBYTES*8，您可能必须制作它们。long你有一个k * next_prime可能会溢出 plain的中间结果int。

就个人而言，由于您是按位索引数组，因此我会以相同的术语设置您的限制以使事情更清楚 - 拥有 a MAXBITS，将数组分配为MAXBITS/32，比较限制和范围的位，并确保您的位数适合进入变量类型。

于 2013-08-18T04:59:48.013 回答