regina::Primes Class Reference
Mathematical Support

A helper class for finding primes and factorising integers. More...

`#include <maths/primes.h>`

## Static Public Member Functions

static unsigned long | size ()
| Returns the number of primes (or suspected primes) currently stored. More...
static Integer | prime (unsigned long which, bool autoGrow=true)
| Returns the requested prime (or suspected prime). More...
static std::vector< Integer > | primeDecomp (const Integer &n)
| Returns the prime factorisation of the given integer as a list of individual primes (or suspected primes). More...
static std::vector< std::pair< Integer, unsigned long > > | primePowerDecomp (const Integer &n)
| Returns the prime factorisation of the given integer as a list of prime powers (or suspected prime powers). More...

## Detailed Description

A helper class for finding primes and factorising integers.

This class has two functions: (i) to maintain a list of known primes, and (ii) to use this list to factorise integers into prime factors.

The primes stored by this class will always be the smallest k suspected primes, where k may grow dynamically as the program runs. Specifically:

- An initial hard-coded list of seed primes is loaded into the class on startup. This list contains precisely the smallest 10,000 primes (the size of this list is subject to change in future versions of Regina).
- Whenever a prime beyond the known list is requested (e.g., when a number greater than the largest stored prime is to be factorised), the list is extended on the fly. The extension uses the probabilistic algorithm shipped with GMP (hence the phrase "suspected primes" above); regarding this algorithm, the GMP documentation states that "for practical purposes it's adequate, the chance of a composite passing will be extremely small."

This list is used by the high-level factorisation routines in this class, such as primeDecomp() and primePowerDecomp(). For users only interested in these high-level routines, there is no need to worry about the size of the list; the high-level routines will extend it if necessary.

Although this class makes use of global data in its implementation, all of its methods are thread-safe.

Author
  Ryan Budney, B.B.

The documentation for this class was generated from the following file:

- maths/primes.h

Copyright © 1999-2016, The Regina development team
This software is released under the GNU General Public License, with some additional permissions; see the source code for details.
For further information, or to submit a bug or other problem, please contact Ben Burton (bab@maths.uq.edu.au).