C/C++ Finding Primes Using the Sieve of Eratosthenes

[SaRaH...]

I have been trying to write a program whose function is to find all of the prime numbers between 0 and n using the "Sieve of Eratosthenes" method. (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) using bit manipulation and bit arrays and the print out the number of primes found, the first five primes and the last five primes. I understand in theory exactly how this works however am having trouble converting that understanding into code. It has to be done using an array of bits which is the problem.

The main steps are as follows:
1. Set the bits representing 0 and 1 to zero and all remaining bits to one. 2. Set count to 0 (the number of found primes so far).
3. Find the first bit in the array that is 1 and assign the value it represents to p (this is a prime number) and increment count.
4. Clear all bits in the array corresponding to multiples of p.
5. Repeat the last two steps until p^2 > n (need to continue until p^2 > n so that the number of primes < N is calculated correctly).

All bits in the array that still have a value of 1 correspond to the prime numbers.

I think I have managed to carry out step one correctly however am now not quite sure how to find the the first bit that has the value of 1 and how to continue from there.

This is a link to the full problem but I'm not certain if it'll work. If not I can post the text:
http://www.scss.tcd.ie/Ivana.Dusparic/2E...b/Lab2.pdf
Any help would be much appreciated.

#define N 100000000 // size of sieve used
#define SIZE ((N+31)/32) //32 bits per integer hard coded
int sieve[SIZE]; //declare array of bits
int count; // count number of primes found

#include <iostream>
#include <iomanip>
#include <time.h>
using namespace std;


void main() {
    int t = clock();

    int array_element;
    int div_result;
    int count=0;

     for(int i = 0; i < SIZE; i++) {
              sieve[i] = 0xFFFFFFFF;                //sets all bits to 1
           }


    sieve[0] = 0xFFFFFFFC;                               //sets first 2 bits to 0


     for (int j = 0; j < SIZE; j++) {                     //loops through each element of the array

         array_element = sieve[j];

         for (int k = 0; k <= 31; k++) {             //loops through each bit of each element of array?               
                
             if (j&1<<k==1) {                       //checks if bit is 1?
                 int p = k;                            //assigns the the bit number to p?
                 cout << p;                          //prints out the bit number?

             }
         }
     }


    cout << "Number of primes less than 100, 000, 000 = " << count << "\n";

    cout << "first 5 primes \n";

    cout << "last 5 primes \n";



      cout << "runtime = " << fixed << setprecision(3) << (double) (clock() - t) / CLOCKS_PER_SEC <<
"s" << endl;
}

 

[rcgldr]

             if (j&1<<k==1) {                       //checks if bit is 1?

There's a precedence issue. Although the binary and operator "&" should have had the same precendence as multiply "*", instead it was given a very low precedence, lower than logical comparasons (which doesn't make sense). The other issues are you want to use array_element, not j, and you're checking for a bits in various positions other than 0:

             if ((array_element & (1<<k)) != 0) {   //checks if bit is 1?

An alternative is:

             if ((array_element>>k) & 1) == 1) {   //checks if bit is 1?

I don't see any code that goes through the sieve to clear out bits that are multiples of prime numbers.

 

[SaRaH...]

So rather than using the for loop that I had:

for (int k = 0; k <= 31; k++) {
				
			 /*if (j&1<<k==1) {
				 int p = k;
				 cout << p;*/
                            }
}

Would it make more sense to use something like this?

for (int k = 0; k <= 31; k++) {if ((array_element & (1<<k)) != 0) {
				 int p = k;
				 if (k != 0) {
					 array_element == 0;
					 cout << p;
				 }

}

Sorry I'm just really not sure where I'm going with this at all as we have never covered it at all and I can't find very much information about it either on the internet or in books. I could do it using an integer array, I'm just struggling to understand how to represent, find and change each bit it code.

 

[D H]

There's a precedence issue. Although the binary and operator "&" should have had the same precendence as multiply "*", instead it was given a very low precedence, lower than logical comparasons (which doesn't make sense).

That it doesn't make any sense is your opinion; it obviously is not the opinion of the standards committee. The standards committee's opinion is the only one that counts; we are stuck with the rules they came up with.

There is of course an out: Use parentheses. Many projects augment the C/C++ precedence table with a rather simple rule: Except for multiplication over addition/subtraction, code that relies the C/C++ precedence rules is invalid code. Always use parentheses.

 

[rcgldr]

Although the binary and operator "&" should have had the same precendence as multiply "*", instead it was given a very low precedence, lower than logical comparasons (which doesn't make sense).

That it doesn't make any sense is your opinion.

Not just mine:

The logical bitwise operators in C (and all programming languages that borrowed precedence rules from C, for example, C++, Perl and PHP) have a precedence level that the author of the language considers to be unsatisfactory.

http://en.wikipedia.org/wiki/Order_of_operations#Programming_languages

Kernighan and Ritchie say ... Some of the operators have the wrong precedence

Some questionable choices of operator precedence, as mentioned by Kernighan and Ritchie above, such as == binding more tightly than & and | in expressions like x & 1 == 0, which would need to be written (x & 1) == 0 to be properly evaluated.

http://en.wikipedia.org/wiki/C_(programming_language)#Syntax

Always use parentheses.

Yes, virtually all programmers will agree with this.