Boost logo

Boost :

From: Daniel Frey (daniel.frey_at_[hidden])
Date: 2003-09-20 06:07:56

Stephen Nutt wrote:
> Since there are around 200 hundred millions prime numbers in the 32 bit
> unsigned integer domain space, and 4e17 primes in the 64 bit integer space,
> I'm trying to find a way to avoid specialisations. My solution now works
> for all 32 bit unsigned numbers, and may even manage number in the teens of
> billions, thought I cannot test this with my compiler.

Just an idea, but "s^(p-1)=s mod p" might still be a solution. We can
use the fact that we have a limited range of numbers to test (32 or 64
bit currently), so we can choose a set of tests that don't create
pseudo-primes (or so few of them that we can specialize them away).

Regards, Daniel

Daniel Frey
aixigo AG - financial training, research and technology
Schloß-Rahe-Straße 15, 52072 Aachen, Germany
fon: +49 (0)241 936737-42, fax: +49 (0)241 936737-99
eMail: daniel.frey_at_[hidden], web:

Boost list run by bdawes at, gregod at, cpdaniel at, john at