// file:    Primes.C
// author:  Robert Keller
// purpose: defining infinite list of primes

#include "Primes.H"

// Prime generator class

// initialize static variables, which are generated on demand

Polylist Primes::oddPrimes = cons(3, Seed(Primes::primesGen, 5));
Polylist Primes::primes = cons(2, oddPrimes);


// primesGen finds next prime >= Candidate and returns list beginning with it
// as first element.  It uses the list oddPrimes, which is being constructed,
// as trial divisors.

Poly Primes::primesGen(Poly Candidate)
  {
  for( integer candidate = Candidate; ; candidate += 2 ) // consider only odds
    {
    for( Polylist trials = oddPrimes; ; trials = trials.rest() )
      {
      integer trial = trials.first();
      if( candidate % trial == 0 )
        break;                                 // not prime, try next candidate
      if( trial*trial > candidate )
        return cons(candidate, Seed(primesGen, candidate+2)); // prime
      }
    }
  }