Implement the Sieve of Eratosthenes and use it to find all prime numbers less than or equal to one million.?

Question

Hey guys, I'm taking a C++ course and I'm having a hard time writing up this code for this question. I could really use your help! Here is the full question:

Implement the Sieve of Eratosthenes and use it to find all prime
numbers less than or equal to one million. Use the result to
prove Goldbach's Conjecture for all even integers between four and
one million, inclusive.

Implement a function with the following declaration:

void sieve(int array[], int num);

This function takes an integer array as its argument. The array
should be initialized to the values 1 through 1000000. The
function modifies the array so that only the prime numbers remain;
all other values are zeroed out.
This function must be written to accept an integer array of any
size. You must should output for all primes numbers between 1 and
1000000, but when I test your function it may be on an array of a
different size.

Implement a function with the following declaration:

void goldbach(int array[], int num);

This function takes the same argument as the previous function
and displays each even integer between 4 and 1000000 with two
prime numbers that add to it.
The goal here is to provide an efficient implementation. This
means no multiplication, division, or modulus when determining if
a number is prime. It also means that the second function must find
two primes efficiently.

Output for your program: All prime numbers between 1 and 1000000
and all even numbers between 4 and 1000000 and the two prime
numbers that sum up to it.


You can also view the entire question here: http://web.njit.edu/~kapleau/teach/current/cs115/project.php#prj2

Answer 1

Your teacher's assignment isn't clear enough and I frankly feel far less motivated because of that fact. In C and C++, arrays start at index 0. The assignment suggests initializing values from 1 through 1000000, but what goes into array[0]? Is that a 1, so that array[999999]= 1000000? Or did the teacher make a mistake and actually want array[1]=1, etc., but forgot to say what should go into array[0]? I don't know. Worse, it's not even important to initialize each array element with the value of its index (or off by 1 from there.) The index itself is sufficient to know the value in this case. Frankly, I consider this a bit ill-conceived and ill-documented. I'll provide an example for the sieve function and leave it to you to figure out how you want to adjust things to suit what you believe the teacher actually wants. But I leave the Goldbach Conjecture to you. I'd rather not write two routines, both of which are wrong because the teacher wasn't clear. I'm assuming also that 'num' refers to the number of elements in array[].



void sieve( int array[], int num ) {

    if ( num < 2 ) return; /* do nothing if nothing to do */

    array[0]= array[1]= 0; /* zero and one are NOT prime */

    for ( int i= 2; i < num; ++i )

        array[i]= i;

    for ( int i= 0; i < num; ++i )

        if ( array[i] != 0 )

            for ( int j= i+i; j < num; j += i )

                array[j]= 0;

}



EDIT: The above code would work equally well if instead of "array[i]= i;" I had written, "array[i]= 1;" Which means a char array would work fine instead of an int array (which is required by the fact that 'i' is assigned instead of just '1'. True and false is all that is needed. The assignment doesn't illustrate even modestly better practice that costs nothing to achieve in terms of added complexity or reduced understandability.

Answer 2

Jonathan makes some good points, and I also think your instructor is not being helpful in requiring you to use an array of int, telling you how to initialize it, etc. With more freedom to design the program yourself, you may be able to come up with a more efficient solution. For this problem, in C++, I like to use a deque. Here's an example:



#include

#include

#include



using namespace std;



void drainSieve(deque&);

void displayPrimes(const deque&);

const size_t N = 1000000;



int main(int argc, char *argv[]) {

    deque sieve(N, true);



    // Find primes

    drainSieve(sieve);



    // Display primes from 0 .. N

    displayPrimes(sieve);



    return 0;

}



void drainSieve(deque &ps) {

    size_t N = ps.size();



    ps[0] = ps[1] = false;

    for (size_t i = 2; i*i < N; i++) {

        if (ps[i] == true) {

            for (size_t j = i+i; j < N; j += i) {

                ps[j] = false;

            }

        }

    }

}



void displayPrimes(const deque &sieve) {

    size_t N = sieve.size();



    for (size_t i = 0, n = 0; i < N; i++) {

        if (sieve[i] == true) {

            cout << setw(8) << i << " ";

            if ((++n % 8) == 0) cout << endl;

        }

    }

}

Answer 3

Jonathan Kapleau