Find primes using sieve of erasthothenes by way of bit arrays in C++

[necromanzer52]

Hey. I have to create a program in C++ to calculate the number of prime numbers up to a specified number. I also have to print out the first and last 5, but I'll cross that bridge when I come to it.

I can do this fine with integers, but we have to do it where each slot in an array represents 32 bits. We have to use bitshifting to make each bit a 1 for a prime, and a 0 for a non-prime. It wasn't explained to us very well how we're supposed to do this, and I can't find any useful information on the internet. Here's what I have so far:

#include <iostream>
using namespace std;

#define N 100 // size of sieve used
#define size ((N+31)/32) //32 bits per integer hard coded
int sieve[size]; //declare array of bits

int main ()
{
int i, j, m, product, count;
count = 0;

for (i=0;i<size;i++)
{
sieve = 0xFFFFFFFF;
}
sieve [0] = 0xFFFFFFFC;

for (j=0;j<32;j++)
{
if (sieve[0] & (1 << j) == 1) //find the next prime
{
count++; //count the prime
product = 0;
for (m=2;product<32;m++) // set each multiple of the prime to 0.
{
product = m*j;

sieve[0] &~(1<<product);

}

}
}



count << count << endl;

return 0;
}

This is just my attempt to count the number of primes in the first 32 numbers, and it just keeps giving an output of 0.
I'm completely lost, and any help would be appreciated.

 

[rcgldr]

C / C++ treat & as lower precendece than == (considered a flaw by some). Use parenthesis to force the order of operations:

		if ((sieve[0] & (1 << j)) == 1)     //find the next prime

 

[necromanzer52]

That changed absolutely nothing.

 

[rcgldr]

It should be:

		if ((sieve[0] & (1 << j)) == (1 << j))     //find the next prime

or

		if ((sieve[0] & (1 << j)) != 0)     //find the next prime

 

[necromanzer52]

Ah. Thanks for that. I think I have it working now.