SaRaH...
Oct8-10, 04:55 PM
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;
}
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;
}