Provided by: libbobcat-dev_3.19.01-1ubuntu1_amd64 #### NAME

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

```

#### SYNOPSIS

```       #include <bobcat/primefactors>

```

#### 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 verb 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.

```

```       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));

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));

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_3.19.01-x.dsc: detached signature;

o      bobcat_3.19.01-x.tar.gz: source archive;

o      bobcat_3.19.01-x_i386.changes: change log;

o      libbobcat1_3.19.01-x_*.deb: debian package holding the libraries;

o      libbobcat1-dev_3.19.01-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’.

```

```       This is free software, distributed under the terms  of  the  GNU  General  Public  License
```       Frank B. Brokken (f.b.brokken@rug.nl).