As ArunMK said, in the second while
loop you mark the prime j
itself as a multiple of j
. And as Lee Meador said, you need to take the modulus of j
modulo 8 for the mask
index, otherwise you access out of bounds and invoke undefined behaviour.
A further point where you invoke undefined behaviour is
while((mark[++j / 8] & mask[j % 8]) != 0);
where you use and modify j
without intervening sequence point. You can avoid that by writing
do {
++j;
}while((mark[j/8] & mask[j%8]) != 0);
or, if you insist on a while
loop with empty body
while(++j, (mark[j/8] & mask[j%8]) != 0);
you can use the comma operator.
More undefined behaviour by accessing mark[MAX/8]
which is not allocated in
for(i = 2;i <= MAX; i++){
and
for(j=0;j<=MAX;j++)
Also, if char
is signed and eight bits wide,
mask[0] |= mask[7] << 7;
is implementation-defined (and may raise an implementation-defined signal) since the result of
mask[0] | (mask[7] << 7)
(the int
128) is not representable as a char
.
But why are you dividing each number by all primes not exceeding the square root of the bound in the second while
loop?
for(i = 2;i <= MAX; i++){
if((i%j) == 0){
That makes your algorithm not a Sieve of Eratosthenes, but a trial division.
Why don't you use the technique from the first while
loop there too? (And then, why two loops at all?)
while (i <= block){
if ((mark[i/8] & mask[i%8]) == 0) {
for (j = 2; i*j < MAX; j++) {
mark[(i*j) / 8] |= mask[((i*j) % 8 )];
}
}
i++;
}
would not overflow (for the given value of MAX
, if that is representable as an int
), and produce the correct output orders of magnitude faster.