Provided by: libbobcat-dev_4.08.02-2build1_amd64

#### NAME

```       FBB::PrimeFactors - Performs the prime-number factorization of (BigInt) values

```

#### SYNOPSIS

```       #include <bobcat/primefactors>
Linking option: -lbobcat

```

#### DESCRIPTION

```       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’. When factorizing a value its prime factors  may  sometimes  repeatedly  be
used as integral divisors: 8 is factorized as pow(2, 3), and 36 is factorized as

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

The  class  FBB::PrimeFactors  performs prime number factorizations of FBB::BigInt values.
When factorizing a value prime numbers up to  sqrt(value)  must  be  available,  as  prime
numbers  up  to sqrt(value) may be factors of value. Currently PrimeFactors uses the sieve
of Eratosthenes to find these  prime  numbers.  To  find  the  next  prime  number  beyond
lastPrime,  the  sieve  of  Eratosthenes  must be used repeatedly for lastPrime += 2 until
lastPrime 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’s sieve PrimeFactors saves all  its  computed  prime
numbers  in  either  a  std::vector or in a file. Once determined, these prime numbers may
again be used when factorizing the next integral value.

After factorizing an integral value its prime number factors  and  associated  powers  are
made  available  in a vector of (PrimeFactors::PrimePower) structs, containing the value’s
sorted prime factors and associated powers.

```

#### NAMESPACE

```       FBB
All constructors, members, operators and manipulators, mentioned  in  this  man-page,  are
defined in the namespace FBB.

```

#### INHERITSFROM

```       -

```

#### TYPEDEFSANDENUMS

```       o      struct PrimePower:
contains two fields:

struct PrimePower
{
BigInt prime;
size_t power;
};

Here, power represents the number of times prime can be used as an integral divisor
of the value that was factorized by PrimeFactors.

o      Factors:
is a synonym for std::vector<PrimePower

```

#### CONSTRUCTORS

```       o      PrimeFactors(BigIntVector &primes):
Prime numbers that were determined while factorizing values are  collected  in  the
BigIntVector that is passed as argument to this constructor.

Initially  the BigIntVector passed as argument may be empty or may contain at least
two primes (which must be, respectively, 2 and 3). The prime numbers in primes must
be  sorted.  The constructor does not verify whether the prime numbers are actually
sorted, but if the BigIntVector contains primes it does check whether the first two
prime  numbers are indeed 2 and 3. An FBB::Exception is thrown if this condition is
not met.

While numbers are being factorized, new prime numbers may be added to  primes,  and
primes can be reused by othher PrimeFactors objects.

o      PrimeFactors(std::string const &name = "~/.primes", size_t blockSize = 1000):
Prime  numbers  that  are  determined  while  factorizing values are collected on a
stream whose name is passed as argument to this constructor. By  default  ~/.primes
is  used. If name starts with `~/’, then this string is replaced by the user’s home
directory.

Primes are read from the named stream in blocks  of  at  most  blockSize,  and  new
primes  are flushed to this stream once blockSize new primes have been generated or
when the PrimeFactors object  (i.e.,  the  last  PrimeFactors  object  sharing  the
stream) ceases to exist.

If  the  stream  does  not  yet exist it is created by PrimeFactors. The stream may
either be empty, or it must contain sorted and white-space delimited prime  numbers
(inserted as hexadecimal BigInt 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 does check whether the
first two prime numbers are indeed 2 and 3. An FBB::Exception  is  thrown  if  this
condition is not met.

While  numbers  are being factorized, new prime numbers may be added to the stream,
and the stream can be reused by other PrimeFactors objects.

The default copy and move constructors are  available.  FBB::PrimeFactor  objects  created
using the copy constructor share the prime numbers storage device (the BigIntVector or the
stream containing the primes) with their source objects.

```

#### OVERLOADEDOPERATORS

```       The  default  copy  and  move  assignment  operators   are   available.   Left-hand   side
FBB::PrimeFactor  objects  receiving  values from right-hand side FBB::PrimeFactor objects
using  the  copy  assignment  operator  share  the  prime  numbers  storage  device   (the
BigIntVector   or   the   stream   containing  the  primes)  with  their  right-hand  side
FBB::PrimeFactors arguments.

```

#### MEMBERFUNCTION

```       o      Factors const &factorize(BigInt const &value):
The prime factors of value are determined and returned in the PrimeFactors::Factors
vectors.  While  the prime factors of value are determined new prime numbers may be
added to the BigIntVector or to the stream  that  is  passed  to  the  PrimeFactors
object.  The  elements  of PrimeFactors::Factors are sorted by their prime numbers.
The first element contains the value’s smallest prime number factor.

```

#### EXAMPLE

```       #include <iostream>
#include <bobcat/primefactors>

using namespace std;
using namespace FBB;

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

cout << "Using /tmp/primes:\n";
for (auto &factor: *factors)
cout << factor.prime << "**" << factor.power << ’ ’;

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

cout << "\n"
"Using BigIntVector:\n";
for (auto &factor: *factors)
cout << factor.prime << "**" << factor.power << ’ ’;

cout << "\n"
"Collected primes: ";

for (auto &prime: primes)
cout << prime << ’ ’;

cout << ’\n’;
}

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

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

```

#### FILES

```       bobcat/primefactors - defines the class interface

```

#### SEEALSO

```       bobcat(7), bigint(3bobcat)

```

#### BUGS

```       None Reported.

```

#### DISTRIBUTIONFILES

```       o      bobcat_4.08.02-x.dsc: detached signature;

o      bobcat_4.08.02-x.tar.gz: source archive;

o      bobcat_4.08.02-x_i386.changes: change log;

o      libbobcat1_4.08.02-x_*.deb: debian package holding the libraries;

o      libbobcat1-dev_4.08.02-x_*.deb: debian package holding the libraries,  headers  and
manual pages;

o      http://sourceforge.net/projects/bobcat: public archive location;

```

#### BOBCAT

```       Bobcat is an acronym of `Brokken’s Own Base Classes And Templates’.

```

#### COPYRIGHT

```       This  is  free  software,  distributed  under  the terms of the GNU General Public License
(GPL).

```

#### AUTHOR

```       Frank B. Brokken (f.b.brokken@rug.nl).
```