# FreeBSD Manual Pages

```FBB::PrimeFactors(3bobcat)    Prime Factorization   FBB::PrimeFactors(3bobcat)

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 in-
tegral  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 factor-
ization,	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 Eratos-
thenes to find these prime numbers. To find the next prime  number  be-
yond  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 num-
bers 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 asso-
ciated powers are made available	in a vector  of	 (PrimeFactors::Prime-
Power) structs, containing the value's sorted prime factors and associ-
ated powers.

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

INHERITS FROM
-

TYPEDEFS AND ENUMS
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	Prime-
Factors.

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 con-
structor 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	block-
Size new primes have been	generated or when the PrimeFactors ob-
ject (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,  re-
spectively, 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 in-
deed 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.

MEMBER FUNCTION
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  BigIntVec-
tor  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

bobcat(7), bigint(3bobcat)

BUGS
None Reported.

DISTRIBUTION FILES
o      bobcat_3.25.01-x.dsc: detached signature;

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

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

o      libbobcat1_3.25.01-x_*.deb:   debian  package  holding  the  li-
braries;

o      libbobcat1-dev_3.25.01-x_*.deb: debian package holding  the  li-

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

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