The Sieve of Eratosthenes and Goldbach's Conjecture

[dadapro]

The Sieve of Eratosthenes

First, write out the numbers from 1 to N. You can write them in a line, or in a square like this (for the numbers 1 to 100):
The number square
First, strike out ("cross out") 1, because 1 is not a prime. Then, strike out all the even numbers except for 2 itself ... because all even numbers greater than 2 divide by two, so cannot be prime. Next, find the smallest number which has not been struck out, i.e., 3. Now strike out every multiple of 3 (except 3 itself), i.e. every third number. Moving on, we find that 4 has been eliminated, but 5 has not. So we strike out all multiples of 5 (except 5 itself), and move on again, repeating in this fashion. Continue until you have eliminated all the composite numbers.

The numbers that remain are the primes!

You may have a grid that looks something like this:
The Sieve of Erathosthenes on the Number Square
This grid shows that 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 are prime.

You may have noticed that all composite numbers in the grid above (the crossed-out numbers) are divisible by 2, 3, 5 or 7. These are the primes which are less than the square root of 100, i.e. 10. In other words, it was only necessary to strike out the powers of 2, 3, 5 and 7 to complete the task for N=100. Can you see why this is? (Hint: The smallest composite number that is not divisible by 2, 3, 5 or 7 is 11 x 11 = 121).






ASSIGNMENT:
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
Update 1: Goldbach's conjecture states that every even integer greater than 2 can be expressed as the sum of two primes.

[AbstractionAnon]

What is your question?

If it is "Will we do your homework for you?", the answer is no.

[dadapro]

i have this code which outputs all prime numbers up to one million, but how do i change it to output all the even number from 4 to one million

#include <iostream>
#include <iomanip>
#include <deque>

using namespace std;

void drainSieve(deque<bool>&);
void displayPrimes(const deque<bool>&);
const size_t N = 1000000;

int main(int argc, char *argv[]) {
    deque<bool> sieve(N, true);

    // Find primes
    drainSieve(sieve);

    // Display primes from 0 .. N
    displayPrimes(sieve);

    return 0;
}

void drainSieve(deque<bool> &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<bool> &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;
        }
    }
}