//
// @file:
//  bsieve.cc
//
// @description:
//
//        Bounded Buffer Seive of Erastophenes.
//
//        Most implementations of the Seive use
//      a simple buffer O(n) in size.  This
//      buffer corresponds to an integer.
//      Starting from 2 on, all multiples
//      of 2 are marked as composite.  Then
//      the next prime 3 on, all multiples
//      of 3 are marked as composite.  And
//      so on.  This approach has a major
//      limitation in that in order to generate
//      n primes, it needs n sized memory buffer.
//      In this implementation, we use
//      a buffer whose size is fixed, i.e.,
//      bounded, and implement the seive
//      in this manner.  The bound on the memory
//      buffer does not limit our ability to
//      generate n primes.
//
// @author:
//
//      rdoss.com
//
#include <iostream>
#include <cstring>
using std::cout;
using std::cerr;
using std::endl;

#include "integer.h"
#include "types.h"
#include "esieve.h"

static const int unit = (1<<20);
static bool prime_tab  [unit];
static integer UNIT = CASTINT(unit);

#define P(symbol) cerr << symbol << endl

//
// esieve:
//
//    Generate primes using a sieve and a list
//  of discovered primes.  Unlike traditional
//  sieve implementations, this approach requires
//  a limited array to mark that the number
//  is a multiple, and a limited by system
//  memory list of primes which is constructed
//  during the sieving process.
//
void esieve( integer max, list_int_t *prime_list )
{
integer start = TWO;
bool found= false;
integer next  = ONE;

memset(prime_tab,0x0,unit);
prime_list->push_back(TWO);
prime_tab[0] = true;
prime_tab[1] = true;

do {
/* Eliminate all duplicates. */
for(integer i = start + start; i < UNIT; i += start) {
prime_tab[i.toUlong()] = true;
}
/* Find another number. */
for(integer i = start+ONE; i < UNIT; i++) {
if(prime_tab[i.toUlong()] == false) {
if(i > max) {
return;
}
prime_list->push_back(i);
start = i;
found = true;
break;
}
}
if(!found) {
break;
} else {
found = false;
}
} while(start < max );

if(start >= max) {
/* We are done. */
return;
}

CONTINUE:

memset(prime_tab,0x0,unit);
/* We have a list of primes up to unit. */
next++;
/* We have to mark this as being
* composite because its a multiple
* of 2048 which is divisible by two.
* Thus, looking at the algorithm
* below, we always skip marking this
* in our prime number generation.
*/
prime_tab[0] = true;
for(list_int_t::iterator i = prime_list->begin();
i != prime_list->end();
i++ ) {
/* Mark which ones in unit * next
* space are multiples of known primes.
*/
for(integer j = (((UNIT * (next-ONE))/(*i)) + ONE) * (*i);
(j - (UNIT * (next-ONE))) < UNIT; j += (*i) ) {
integer index = j - (UNIT * (next-ONE));
prime_tab[index.toUlong()] = true;
}
}
/* So long as the square root of
* (unit * next) is less than
* the largest number in (unit * (next-1))
* we can just grab all the numbers
* marked false.  This is because
* we are working linearly not
* exponentially.  If we were working
* exponentially, we would have
* to write code that would
* take the first 'false' element,
* place it in the prime_list and
* mark out its multiples.
* However, the purpose of this
* is to implement a seive that does
* not require O(N) sized memory buffer
* to determine the primes.
* Therefore, expanding the
* field exponentially is not
* valid.
*/
for(integer i = ZERO; i < UNIT; i++) {
if(prime_tab[i.toUlong()] == false) {
prime_list->push_back(i + (UNIT * (next-ONE)));
if(i + (UNIT * (next-ONE)) > max) {
return;
}
}
}
goto CONTINUE;

}// esieve
//
// EOF
//