Lazy Primes in C++


#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!

>>4
I know that isPrime() is simple and expensive. At least it's somewhat "optimized" by only going up to the square root....

Wait, I could possibly make this better by using the existing list of prime numbers to determine whether the next number is prime.

Anyways, like I said, in some short tests, I found isqrt() to be just as fast as (unsigned long)sqrt().