Name: Anonymous 2009-03-31 18:31
#include <cstdlib>
#include <climits>
#include <unistd.h>
class Prime
{
unsigned long value;
Prime* next;
bool locked;
// modified from
// www.codecodex.com/wiki/index.php?title=Calculate_an_integer_square_root
static unsigned long isqrt(unsigned long n)
{
register unsigned long op = n, res = 0, one;
// second-to-top bit set portably.
one = (~((ULONG_MAX << 1) >> 1)) >> 1;
while(one > op) one >>= 2;
while(one) {
if(op >= res + one) {
op = op - (res + one);
res = res + 2 * one;
}
res >>= 1;
one >>= 2;
}
return res;
}
// used to test primality of larger integers.
static bool isPrime(unsigned long n)
{
unsigned long i, j = isqrt(n);
// if n is cleanly divisible once from 3 to isqrt(n),
// then it is not prime.
for(i = 3; i <= j; i += 2)
if(n % i == 0)
return false;
// if never cleanly divisible, then n is prime.
return true;
}
// used so that only one thread will generate the next prime at a time.
void lock()
{
while(locked)
usleep(0);
locked = true;
}
// lets other threads get the next prime once it's been generated.
void unlock()
{
locked = false;
}
// don't let primes be copied--that's just asking for memory allocation
// woes.
Prime(const Prime&);
public:
Prime(unsigned long v, Prime *n = NULL)
: value(v), next(n), locked(false)
{
}
~Prime()
{
delete next;
}
Prime* Next()
{
if(!next)
{
unsigned long i;
lock();
// search for the next prime;
for(i = value + 2; !isPrime(i) && i < ULONG_MAX - 1; i += 2);
// if the search was good, we've generated the next prime.
if(i != ULONG_MAX - 1)
next = new Prime(i);
unlock();
}
return next;
}
unsigned long Value() const
{
return value;
}
};
class Primes
{
Prime* first;
public:
Primes() : first(new Prime(2, new Prime(3)))
{
}
~Primes()
{
delete first;
}
Prime* First()
{
return first;
}
};Primes on demand!