bionic (3) primefactors.3bobcat.gz
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.
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 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.
OVERLOADED OPERATORS
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 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
SEE ALSO
bobcat(7), bigint(3bobcat)
BUGS
None Reported.
DISTRIBUTION FILES
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).