.TH "FBB::PrimeFactors" "3bobcat" "2005\-2020" "libbobcat\-dev_5\&.07\&.00" "Prime Factorization"

.PP 
.SH "NAME"
FBB::PrimeFactors \- Performs the prime\-number factorization of
(BigInt) values
.PP 
.SH "SYNOPSIS"
\fB#include <bobcat/primefactors>\fP
.br 
Linking option: \fI\-lbobcat\fP 
.PP 
.SH "DESCRIPTION"

.PP 
Integral values fall into two categories: prime numbers, whose only
integral divisors are their own values and 1, and composite numbers, which
also have at least one other (prime number) integral divisor\&. All composite
integral values can be factorized as the product of prime numbers\&. E\&.g\&., 6 can
be factorized as 2 * 3; 8 can be factorized as 2 * 2 * 2\&. Finding these prime
factors is called the prime number factorization, or `prime
factorization\(cq\&\&. When factorizing a value its prime factors may sometimes
repeatedly be used as integral divisors: 8 is factorized as \fIpow(2, 3)\fP, and
36 is factorized as
.nf 

    36 = pow(2, 2) * pow(3, 2)
        
.fi 

.PP 
The class \fBFBB::PrimeFactors\fP performs prime number factorizations of
\fIFBB::BigInt\fP values\&. When factorizing a value prime numbers up to
\fIsqrt(value)\fP must be available, as prime numbers up to \fIsqrt(value)\fP may
be factors of \fIvalue\fP\&. Currently \fIPrimeFactors\fP uses the sieve of
Eratosthenes to find these prime numbers\&. To find the next prime number beyond
\fIlastPrime\fP, the sieve of Eratosthenes must be used repeatedly for
\fIlastPrime += 2\fP until \fIlastPrime\fP is prime\&. Once determined, prime
numbers can of course be used directly to determine the next prime number or
to factorize an integral value\&. To accellerate prime number factorization and
Eratosthenes\(cq\&s sieve \fBPrimeFactors\fP saves all its computed prime numbers in
either a \fIstd::vector\fP or in a file\&. Once determined, these prime numbers
may again be used when factorizing the next integral value\&.
.PP 
After factorizing an integral value its prime number factors and
associated powers are made available in a vector of
(\fIPrimeFactors::PrimePower\fP) structs, containing the value\(cq\&s sorted prime
factors and associated powers\&.
.PP 
.SH "NAMESPACE"
\fBFBB\fP
.br 
All constructors, members, operators and manipulators, mentioned in this
man\-page, are defined in the namespace \fBFBB\fP\&.
.PP 
.SH "INHERITS FROM"
\-
.PP 
.SH "TYPEDEFS AND ENUMS"

.PP 
.IP o 
\fBstruct PrimePower\fP:
.br 
contains two fields:
.nf 

    struct PrimePower
    {
        BigInt prime;
        size_t power;
    };
        
.fi 
Here, \fIpower\fP represents the number of times \fIprime\fP can be used
as an integral divisor of the value that was factorized by \fBPrimeFactors\fP\&.
.IP 
.IP o 
\fBFactors\fP:
.br 
is a synonym for \fIstd::vector<PrimePower\fP

.PP 
.SH "CONSTRUCTORS"
.IP o 
\fBPrimeFactors(BigIntVector &primes)\fP:
.br 
Prime numbers that were determined while factorizing values are
collected in the \fIBigIntVector\fP that is passed as argument to this
constructor\&. 
.IP 
Initially the \fIBigIntVector\fP passed as argument may be empty or may
contain at least two primes (which must be, respectively, 2 and 3)\&. The prime
numbers in \fIprimes\fP must be sorted\&. The constructor does not verify whether
the prime numbers are actually sorted, but if the \fIBigIntVector\fP contains
primes it \fIdoes\fP check whether the first two prime numbers are indeed 2 and
3\&. An \fIFBB::Exception\fP is thrown if this condition is not met\&.
.IP 
While numbers are being factorized, new prime numbers may be added to
\fIprimes\fP, and \fIprimes\fP can be reused by othher \fIPrimeFactors\fP objects\&.
.IP 
.IP o 
\fBPrimeFactors(std::string const &name = \(dq\&~/\&.primes\(dq\&, size_t blockSize =
1000)\fP:
.br 
Prime numbers that are determined while factorizing values are
collected on a stream whose name is passed as argument to this constructor\&. By
default \fI~/\&.primes\fP is used\&. If \fIname\fP starts with `\fI~/\fP\(cq\&, then this
string is replaced by the user\(cq\&s home directory\&. 
.IP 
Primes are read from the named stream in blocks of at most \fIblockSize\fP,
and new primes are flushed to this stream once \fIblockSize\fP new primes have
been generated or when the \fBPrimeFactors\fP object (i\&.e\&., the last
\fBPrimeFactors\fP object sharing the stream) ceases to exist\&.
.IP 
If the stream does not yet exist it is created by \fBPrimeFactors\fP\&. The
stream may either be empty, or it must contain sorted and white\-space
delimited prime numbers (inserted as hexadecimal \fIBigInt\fP values)\&. The first
two primes on this file must be, respectively, 2 and 3\&. The constructor does
not verify whether the prime numbers are actually sorted, but if the stream
contains primes it \fIdoes\fP check whether the first two prime numbers are
indeed 2 and 3\&. An \fIFBB::Exception\fP is thrown if this condition is not met\&.
.IP 
While numbers are being factorized, new prime numbers may be added to the
stream, and the stream can be reused by other \fIPrimeFactors\fP objects\&.

.PP 
Copy and move constructors (and assignment operators) are available\&.
.PP 
\fBFBB::PrimeFactor\fP objects created using the copy constructor or
receiving their values using the copy assignment operator share the prime
numbers storage device (the \fIBigIntVector\fP or the stream containing the
primes) with their source objects\&.
.PP 
.SH "MEMBER FUNCTION"

.PP 
.IP o 
\fBFactors const &factorize(BigInt const &value)\fP:
.br 
The prime factors of \fIvalue\fP are determined and returned in the
\fIPrimeFactors::Factors\fP vectors\&. While the prime factors of \fIvalue\fP are
determined new prime numbers may be added to the \fIBigIntVector\fP or to the
stream that is passed to the \fBPrimeFactors\fP object\&. The elements of
\fIPrimeFactors::Factors\fP are sorted by their prime numbers\&. The first element
contains the value\(cq\&s smallest prime number factor\&.

.PP 
.SH "EXAMPLE"

.PP 
.nf 
#include <iostream>
#include <bobcat/primefactors>

using namespace std;
using namespace FBB;

int main(int argc, char **argv)
{
    PrimeFactors pf1(\(dq\&/tmp/primes\(dq\&);
    PrimeFactors::Factors const *factors = &pf1\&.factorize(stoull(argv[1]));

    cout << \(dq\&Using /tmp/primes:\en\(dq\&;
    for (auto &factor: *factors)
        cout << factor\&.prime << \(dq\&**\(dq\& << factor\&.power << \(cq\& \(cq\&;

    vector<BigInt> primes;
    PrimeFactors pf2(primes);
    factors = &pf2\&.factorize(stoull(argv[1]));

    cout << \(dq\&\en\(dq\&
            \(dq\&Using BigIntVector:\en\(dq\&;
    for (auto &factor: *factors)
        cout << factor\&.prime << \(dq\&**\(dq\& << factor\&.power << \(cq\& \(cq\&;

    cout << \(dq\&\en\(dq\&
            \(dq\&Collected primes: \(dq\&;

    for (auto &prime: primes)
        cout << prime << \(cq\& \(cq\&;

    cout << \(cq\&\en\(cq\&;
}    



.fi 

.PP 
If this program is run with argument 1950 it produces the following
output: 
.nf 

    Using /tmp/primes:
    2**1 3**1 5**2 13**1 
    Using BigIntVector:
    2**1 3**1 5**2 13**1 
    Collected primes: 2 3 5 7 11 13 
        
.fi 

.PP 
.SH "FILES"
\fIbobcat/primefactors\fP \- defines the class interface
.PP 
.SH "SEE ALSO"
\fBbobcat\fP(7), \fBbigint\fP(3bobcat)
.PP 
.SH "BUGS"
None Reported\&.
.PP 
.SH "BOBCAT PROJECT FILES"

.PP 
.IP o 
\fIhttps://fbb\-git\&.gitlab\&.io/bobcat/\fP: gitlab project page;
.IP o 
\fIbobcat_5\&.07\&.00\-x\&.dsc\fP: detached signature;
.IP o 
\fIbobcat_5\&.07\&.00\-x\&.tar\&.gz\fP: source archive;
.IP o 
\fIbobcat_5\&.07\&.00\-x_i386\&.changes\fP: change log;
.IP o 
\fIlibbobcat1_5\&.07\&.00\-x_*\&.deb\fP: debian package containing the
libraries;
.IP o 
\fIlibbobcat1\-dev_5\&.07\&.00\-x_*\&.deb\fP: debian package containing the
libraries, headers and manual pages;

.PP 
.SH "BOBCAT"
Bobcat is an acronym of `Brokken\(cq\&s Own Base Classes And Templates\(cq\&\&.
.PP 
.SH "COPYRIGHT"
This is free software, distributed under the terms of the 
GNU General Public License (GPL)\&.
.PP 
.SH "AUTHOR"
Frank B\&. Brokken (\fBf\&.b\&.brokken@rug\&.nl\fP)\&.
.PP