Boost logo

Boost :

From: Stephen Nutt (snutt_at_[hidden])
Date: 2003-09-17 21:09:09

I've uploaded 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

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.


Prime.hpp defines the following templates
template <unsigned x, unsigned y> struct power;
unsigned a = power<5, 3>::val; // Compile time calculation of 5^3

template <unsigned x, unsigned y> struct root;
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
bool isPrime = is_prime <7>::val;
 BOOST_STATIC_ASSERT (is_prime<table_size>::val);

template<unsigned x> struct greatest_prime_less_or_equal;
unsigned prime = greatest_prime_less_or_equal<21>; // prime will be 19

template<unsigned x> struct smallest_prime_greater_or_equal;

unsigned prime = smallest_prime_greater_or_equal<21>; // prime will be 23

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, gregod at, cpdaniel at, john at