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!

>>10
it's pretty obvious that the call to the square root function is the only thing in the body of the loop, the result is discarded, and i isn't used after the loop. unless your libc is completely braindead and doesn't declare atoi and sqrt with the const attribute, even the shittiest compiler in widespread use should be able to eliminate the whole loop.