Prime generating with bit masking is causing programme to crash

Question

In the below code, I have used bitmasking for generating primes butunfortunately it doesn't work properly rather this programme is crashing while running.

#include <bits/stdc++.h>
#define maxn 65540
using namespace std;

int _c[(maxn>>6)+1];  //as we will be neede max

int  primes[maxn];


#define IsComp(n)  (_c[n>>6]&(1<<((n>>1)&31)))//to compare bit
#define SetComp(n) _c[n>>6]|=(1<<((n>>1)&31))//to set the bit
void prime_sieve() {
for (int i = 3; i <=maxn; i += 2)
    if (!IsComp(i))
        for (int j = i*i; j <=maxn; j += i+i)
            SetComp(j);//if the number is not primes then it is changed     to  1

primes[0]=2;//first prime is 2;
int   j=1;
for (int i=3; i <= maxn; i += 2)
    if (!IsComp(i))
        primes[j++]=i;//putting the value in primes array;
}
int main()
{

prime_sieve();//calling the function
//Prime();
}

It helps to provide details on how the code crashes? Is it not compiling or giving you a runtime error? — Ammar Husain, Apr 16 '16 at 16:51
@AmmarHusain code it compiling but i think while generating those primes the code on my IDE is crashing..by the way thanks for your response. — leonel shovo, Apr 16 '16 at 16:56
What exactly is going wrong? And your code formatting is rather horrendous. Also, using global variables is bad practice. And lambdas or function objects should be used rather than macros. — Charles, Apr 16 '16 at 17:09
@c650 thanks for ur concern ,next time i will try to avoid this and again thanks for your advice — leonel shovo, Apr 16 '16 at 18:18
What's `MAX`? It doesn't appear to be defined anywhere in your code. — Igor Tandetnik, Apr 16 '16 at 18:53
@IgorTandetnik thanks for correcting me..but still have the problem :( — leonel shovo, Apr 17 '16 at 13:44
My eyes hurt! Also: http://stackoverflow.com/q/31816095/560648 — Lightness Races in Orbit, Apr 17 '16 at 14:14
if you have found the answer you can post it as answer@leonelshovo — Zahan Safallwa, Apr 17 '16 at 14:54

score 1 · Accepted Answer · answered Apr 17 '16 at 14:12

From what i can understand When the outer loop (i) runs until 46348 It works well as i*i is under the range 2147483648 but when i becomes 46349 there is integer overflow in j value and it's value becomes -2146737495 and then follows setComp(j) with j as negative.

Prime generating with bit masking is causing programme to crash

1 Answers1