
Boost : 
From: Stephen Nutt (snutt_at_[hidden])
Date: 20030917 21:09:09
I've uploaded Prime.zip to yahoo. It contains two files. The first one
checks the primality of a number at compile time, and can also be used to
generate a prime number at compile time, either >= or <= to a starting
number. It also contains a couple of useful templates to generate compile
time powers and roots. Powers aren't too interesting, but the roots I
thought were elegant.
The second file just contains hundreds of BOOST_STATIC_ASSERT to check the
primality of known values.
When dealing with large numbers of more than a few million I needed to
increase my compiler heap size. Once increased I can check the primality of
numbers over 450 million. Being able to generate prime numbers from a
starting point is very dependant upon how quickly it can find a prime, or
determine the false candidates are not prime. I have success in the low
tens of millions, but quickly run into compiler limitations when up around
50 million. My compiler is MSVC 6.0, and other compiles may fare better or
worse.
Please send feedback. If someone can figure out how to do this with
Fermat's little theorem, it may be possible to do even better when
generating prime numbers.
Stephen
Prime.hpp defines the following templates
template <unsigned x, unsigned y> struct power;
Usage
unsigned a = power<5, 3>::val; // Compile time calculation of 5^3
template <unsigned x, unsigned y> struct root;
Usage
unsigned a = root<125, 3>::val; // Compile time calculation of the cubed
root of 125
template<unsigned x> struct square_root;
template<unsigned x> struct cubed_root;
Shortcuts to root<x, 2> and root<x, 3> respectively
template<unsigned x> struct is_prime
Usage
bool isPrime = is_prime <7>::val;
or
BOOST_STATIC_ASSERT (is_prime<table_size>::val);
template<unsigned x> struct greatest_prime_less_or_equal;
Usage
unsigned prime = greatest_prime_less_or_equal<21>; // prime will be 19
template<unsigned x> struct smallest_prime_greater_or_equal;
Usage
unsigned prime = smallest_prime_greater_or_equal<21>; // prime will be 23
PrimeTest.cpp
Contains 16 test to check the templates is_prime,
greatest_prime_less_or_equal and smallest_prime_greater_or_equal
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk