compute_primes.cpp

//  compute_primes.cpp

// This is the class-based solution

#include <algorithm>        // std::set_difference, std::find_if
#include <iostream>
#include <iterator>         // std::inserter
#include <vector>

#include "compute_primes.h"

compute_primes::compute_primes() : last_factor(1)
{}

int compute_primes::sequence()
{
    return last_sequence++;
}

std::set<int> compute_primes::operator()(int N)
{
    // clear data from any previous runs
    series.clear();
    non_prime.clear();
    last_factor = 1;
    last_sequence = 2;

    //----------------------------------------------------------------
    // fill with sequence of potentially prime numbers from 2 to N.
    // we skip over 1 b/c, by definition, 1 cannot be a prime number
    // credits: https://stackoverflow.com/a/19529648

    // first fill the collection with a monotonic sequence of numbers
    std::generate_n(
                        inserter(series, series.end()),
                        N+1,
                        [&]{ return series.size(); }
                   );

    // the first number cannot be less than 2.
    // Toss the numbers less than 2.
    // credits: https://stackoverflow.com/a/19529648
    series.erase( series.begin(), series.find(2) );
    //----------------------------------------------------------------

    // Eratosthenes' algorithm begins with the smallest
    // prime number, 2, and computes its factors up to some
    // max limit.
    //
    // Eratosthenes' algorithm then advances to the next
    // higher prime number and again computes its
    // factors up to some max limit. The algorithm loops
    // on this step until encountering the max limit.


    // now compute the non-prime numbers up to N
    do
    {
        // get largest larger prime number
        const int next_prime = get_next_prime();

        // calculate all of the next_prime's factors up N
        compute_non_primes( next_prime, N );

        if (next_prime >= N)
        {
            break;
        }

    } while (true);

    std::set<int> retval;

    // credits: https://stackoverflow.com/a/16079838
    // now create a table of prime numbers by removing
    // the calculated non-prime numbers from the
    // table filled with a sequence of numbers.
    std::set_difference(series.begin(),       series.end(),
                        non_prime.begin(),    non_prime.end(),
                        std::inserter(retval, retval.begin()) );

    return retval;

}

//
int compute_primes::get_next_prime()
{
    // Advance upward from the last prime number looking for
    // number that is not yet in the table of non-prime numbers.
    //
    // Such a number ought to be a prime number
    do
    {
        last_factor++;
    } while  (non_prime.end() != non_prime.find(last_factor) );

    // return the next higher prime number
    return last_factor;
}

// One step in Eratosthenes' sieve depends on generating a sequence of
// non-prime numbers for a given factor. This sequence is generated by
// multiplying the factor (a known prime number) by 2, then 3, and so on, until the
// product is greater than the goal, say, compute all non-primes up to N.
void compute_primes::compute_non_primes(int factor, int limit )
{

    for (int i = 2; i < limit; i++)
    {
        // compute non-prime number
        const int next_candidate = i*factor;

        // if the non-prime number is beyond the limit
        if (next_candidate > limit)
        {
            break; // eject
        }

        // add to collection of non-prime numbers
        non_prime.insert(next_candidate);
    }
}