Finding Prime Numbers with Sieve of Eratosthenes(C++)

[Mr. Mojo Risin]

I'm trying to do an exercise to find prime numbers using The Sieve of Eratosthenes in C++. I have been working at this for hours and can't get it to work right, so maybe someone can help? I don't know if I'm close or totally off. There's some extra code I put in here to kinda debug things by printing variables and the array, but I'm still lost. My approach is to use a two-dimensional array. The first row has either a 1 or 0. A 1 means the number in the corresponding second row is a prime number. As I understand it, The Sieve approach has you mark multiples of 2 and then 3, etc.

Here's the code I have so far:


#include <iostream>
using namespace std;

void initializeArray(int primeNumbers[][500]);
void findPrimeNumbers(int primeNumbers[][500]);
void printPrimes(int primeNumbers[][500]);

int main()
{
int primeNumbers[2][500];

initializeArray(primeNumbers);
findPrimeNumbers(primeNumbers);
//printPrimes(primeNumbers);
for (int j = 0; j < 500; j++)
cout << " " << primeNumbers[0][j];

return 0;
}


void initializeArray(int primeNumbers[][500])
{
for (int x = 0; x < 500; x++){
primeNumbers[0][x] = 1;
primeNumbers[1][x] = x;
}
}

void findPrimeNumbers(int primeNumbers[][500])
{
for (int x = 2; x < 499; x++){
cout << " x is " << x;
if (primeNumbers[0][x] == 1){
int z = primeNumbers[1][x];
cout << " z = " << z;
for (int y = primeNumbers[1][x]; y <= 500; y += z){
cout << " y is " << y;
primeNumbers[0][y + y] = 0;
}
}
}
}

void printPrimes(int primeNumbers[][500])
{
for (int x = 0; x < 500; x++){
if (primeNumbers[0][x] == 1)
cout << primeNumbers[1][x] << " is a prime number" << endl;
}
}

[Mr. Mojo Risin]

a. A prime integer is any integer that is evenly divisible only by itself and 1. The Sieve of Eratosthenes is a method of finding prime numbers. It operates as follows:
b. Create an array with all elements initialized to 1 (true). Array elements with prime subscripts will remain 1. All other array elements will eventually be set to zero.
c. Starting with array subscript 2 (Subscript 1 must be prime), every time an array element is found whose value is 1, loop through the remainder of the array and set to zero every element whose subscript is a multiple of the subscript for the element with value 1. For array subscript 2, all elements beyond 2 in the array that are multiples of 2 will be set to zero (subscripts 4, 6, 8, 10, etc…); For array subscript 3, all elements beyond 3 in the array that are multiples of 3 will be set to zero (subscripts 6, 9, 12, 15, etc…); and so on.
d. When the process is complete, the array elements that are still set to one indicate that the subscript is a prime number. These subscripts can then be printed

[JimCevera]

I have made corrections to this code, with comments. I added a counter and changed the array size from 500 to 75000. With the displays commented out, the results are almost immediate. Here is the altered code:

#include <iostream>
using namespace std;

void initializeArray(int primeNumbers[][75000]);
void findPrimeNumbers(int primeNumbers[][75000]);
void printPrimes(int primeNumbers[][75000]);

int a = 0; // prime counter

int main()
{
int primeNumbers[2][75000];

initializeArray(primeNumbers);
findPrimeNumbers(primeNumbers);
printPrimes(primeNumbers);
/* for (int j = 0; j < 75000; j++)
if (primeNumbers[0][j] == 1)
cout << "\n " << primeNumbers[0][j] << " " << primeNumbers[1][j];
*/
cout << "\n" << a << " Total Prime Numbers\n";
system("PAUSE");
return 0;
}


void initializeArray(int primeNumbers[][75000])
{
primeNumbers[0][0] = 0;
primeNumbers[0][1] = 0;
primeNumbers[0][1] = 0;
primeNumbers[1][1] = 1;
for (int x = 2; x < 75000; x++){
primeNumbers[0][x] = 1;
primeNumbers[1][x] = x;
}
}

void findPrimeNumbers(int primeNumbers[][75000])
{
for (int x = 2; x = 75000/2; x++){
/* going beyond 1/2 of array is wasting CPU */

// cout << " x is " << x;
if (primeNumbers[0][x] == 1){
int z = primeNumbers[1][x];
// cout << " z = " << z;
/* for (int y = primeNumbers[1][x]; y <= 500; y += z){

you want your starting point to be twice the x value
so any of 'y = z * 2' or 'y = x = z' or 'y = x * 2'
will work
*/
for (int y = x + z; y <= 75000; y += z){
// cout << " y is " << y;
primeNumbers[0][y] = 0;
}
}
}
}

void printPrimes(int primeNumbers[][75000])
{
for (int x = 0; x < 75000; x++){
if (primeNumbers[0][x] == 1){
/* added counter */
a++;
cout << primeNumbers[1][x] << " is a prime number" << endl;
}
}
}