1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Oct 9, 2012 #1
    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);

    }

    }
    }



    cout << 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.
     
  2. jcsd
  3. Oct 9, 2012 #2

    rcgldr

    User Avatar
    Homework Helper

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

    Code (Text):

            if ((sieve[0] & (1 << j)) == 1)     //find the next prime
     
     
  4. Oct 9, 2012 #3
    That changed absolutely nothing.
     
  5. Oct 9, 2012 #4

    rcgldr

    User Avatar
    Homework Helper

    It should be:

    Code (Text):

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

            if ((sieve[0] & (1 << j)) != 0)     //find the next prime
     
     
  6. Oct 10, 2012 #5
    Ah. Thanks for that. I think I have it working now.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Find primes using sieve of erasthothenes by way of bit arrays in C++
  1. Array C++ (Replies: 2)

  2. C - array (Replies: 2)

Loading...