Regina Calculation Engine

A helper class for finding primes and factorising integers. More...
#include <maths/nprimes.h>
Static Public Member Functions  
static unsigned long  size () 
Returns the number of primes (or suspected primes) currently stored. More...  
static NLargeInteger  prime (unsigned long which, bool autoGrow=true) 
Returns the requested prime (or suspected prime). More...  
static std::vector< NLargeInteger >  primeDecomp (const NLargeInteger &n) 
Returns the prime factorisation of the given integer as a list of individual primes (or suspected primes). More...  
static std::vector< std::pair < NLargeInteger, unsigned long > >  primePowerDecomp (const NLargeInteger &n) 
Returns the prime factorisation of the given integer as a list of prime powers (or suspected prime powers). More...  
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:
This list is used by the highlevel factorisation routines in this class, such as primeDecomp() and primePowerDecomp(). For users only interested in these highlevel routines, there is no need to worry about the size of the list; the highlevel routines will extend it if necessary.

static 
Returns the requested prime (or suspected prime).
More specifically, this routine returns the (which + 1)th smallest prime. Thus prime(0) returns 2, prime(1) returns 3, prime(2) returns 5, and so on.
If which is smaller than the number of initial seed primes, the result is guaranteed to be the (which + 1)th smallest prime (see the NPrimes class notes for the size of the initial seed list). If which is larger, a probabilistic algorithm is used and so there is a possibility that nonprimes are included in the list.
If which < size() then this routine is essentially instantaneous, since the (which + 1)th smallest (suspected) prime is already stored. Otherwise the behaviour depends on the argument autoGrow. If autoGrow is true
(the default) then this routine calculates the requested prime, which might take some time. If autoGrow is false
then this routine returns zero.
which  indicates which prime is requested. 
autoGrow  specifies what to do if the requested prime lies beyond the list currently stored (see above). 
false
.

static 
Returns the prime factorisation of the given integer as a list of individual primes (or suspected primes).
Prime factors are returned in increasing order. Where a prime power appears in the factorisation, the relevant prime will appear several times in the list.
For very large integers, the factorisation becomes probabilistic: (i) this routine examines suspected primes instead of primes (see the class notes), and (ii) if the routine is having trouble finding factors then it will run a probabilistic prime test on whatever portion of n still remains (and will assume that portion to be prime if the test passes).
The given integer may be negative, in which case 1 will be listed as the first factor (even though 1 is not prime). If 0 is passed then a single factor of 0 will be returned; if 1 is passed then an empty list will be returned. In all cases, the given integer n will be the product of all elements of the final list (where an empty product is assumed to be 1).
As an example, the prime factors of 54 will be listed as (2, 3, 3, 3), and the prime factors of 90 will be listed as (1, 2, 3, 3, 5).
Note that the internal list of known primes and suspected primes will be expanded as necessary; there is no need for the caller to manage this list manually.
n  the integer to factorise. 

static 
Returns the prime factorisation of the given integer as a list of prime powers (or suspected prime powers).
Factors are returned as (prime, exponent) pairs. Different pairs describe different primes, and the pairs are sorted in order from smallest prime to largest. All exponents are strictly positive.
For very large integers, the factorisation becomes probabilistic: (i) this routine examines suspected primes instead of primes (see the class notes), and (ii) if the routine is having trouble finding factors then it will run a probabilistic prime test on whatever portion of n still remains (and will assume that portion to be prime if the test passes).
The given integer may be negative, in which case (1,1) will be listed as the first prime power (even though 1 is not prime). If 0 is passed then a single pair (0,1) will be returned; if 1 is passed then an empty list will be returned. In all cases, the given integer n will be the product of all powers described by the final list (where an empty product is assumed to be 1).
As an example, the factorisation of 54 will be reported as [(2,1) (3,3)], and the factorisation of 90 will be reported as [(1,1) (2,1) (3,2) (5,1)].
Note that the internal list of known primes and suspected primes will be expanded as necessary; there is no need for the caller to manage this list manually.
The current implementation of this routine merely calls primeDecomp() and rewrites the list of factors by grouping primes.
n  the integer to factorise. 

inlinestatic 
Returns the number of primes (or suspected primes) currently stored.
Primes that are already stored can be accessed instantly; primes larger than those currently stored must be generated on the fly (which takes time).
This number may increase as the program runs (according to whether larger primes are requested), but it will never decrease.