I haven't actually been following this thread, but as a "relax" exercise, I tried to write myself an "is prime" function off the top of my head. My first thought was a sieve approach.
I first wrote a function that maintained a static internal std::set<>, but then I thought it might be nice to have access to that set outside of just checking to see if a number is prime.
#include <ciso646>
#include <set>
#include <boost/foreach.hpp>
#define foreach BOOST_FOREACH
template <typename T = unsignedlongint>
struct primes: public std::set <T>
{
// The list of primes is partitioned into lower primes (which are all
// sequential) and higher primes (which are not necessarily sequential, but
// were found to be prime by previous invocations of this algorithm).
//
// When updating the list, we need to start with the next possible
// sequential prime, so as not to miss anything. Since our list is actually
// a set, adding a prime from the 'higher primes' partition has the effect
// of simply transferring it to the 'lower primes' partition.
//
// We track the partitions by simply remembering the largest prime number
// in the 'lower primes' partition.
//
T last_sequential;
primes()
{
this->insert( 2 );
this->insert( 3 );
this->insert( 5 );
last_sequential = 5;
}
bool isprime( const T& n )
{
if (n < 2) returnfalse;
if (this->count( n )) returntrue;
// Does (any known prime p) divide n?
foreach (const T& p, *this)
{
if ((n % p) == 0) returnfalse;
}
// Did we check all possible primes <= sqrt( n )?
// If not, we need to grow our 'lower primes' partition.
T p = last_sequential;
while ((n / p) > p)
{
p += 2;
if (isprime( p ))
{
last_sequential = p;
// Is the new found prime a divisor of n?
if ((n % p) == 0) returnfalse;
}
}
// If we get this far, then n is prime.
// Add it to our 'higher primes' partition.
this->insert( n );
returntrue;
}
};
There are a few other checks I could have put in there.. but it works pretty quickly for any n ten digits long or less. (It fails for larger numbers, but I'm not sure why... I haven't investigated yet.)
I was pretty pleased with myself until I realized there are are much quicker methods of finding primes than using E's sieve.