Reputation: 619
I'm learning C. For a school assignment, I wrote some code to print prime numbers within a certain range. I use 50000 as the maxbyte for a bit-array. My code compiles, but it gives me an error called "segmentation fault:11" (It stops at 46337). Can someone tell me what the problem is in my code? How can I fix this error? Thank you.
#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);
}
}
Upvotes: 1
Views: 4797
Reputation: 13196
First thing to do is make up your mind about what MAXBYTES
actually means. Since you allocate the array bit_arr
to have that many ints, not bytes, you're allocating 4 times the memory you need and just wasting it. Also, you're allocating it as a local on the stack--many machines won't have that much space on the stack, which is probably why it fails with a bigger number. Better to either make it static or allocate it on the heap with malloc()
.
Also, you need to take more care about the ranges of the numbers used: i
and k
, for example, may be up to MAXBYTES*8
, so you may have to make them long
if you increase it. And you have an intermediate result k * next_prime
that might overflow plain int
.
Personally, since you are indexing the array by bits, I would set your limits in those same terms to make things clearer--have a MAXBITS
, allocate the array as MAXBITS/32
, compare limits and ranges in terms of bits, and make sure your bit counts fit into the variable types.
Upvotes: 2
Reputation: 4411
In while(next_prime*k < MAXBYTES*8)
The largest value for next_prime*k
is (MAXBYTES*8-1)*(MAXBYTES*8-1)
.
This large value can't hold in a signed int
and may turn into a negative value causing a segfault.
Using
while(unsigned(next_prime*k) < MAXBYTES*8)
would eliminate the segfault.
Upvotes: 3