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_3.23.01-x.dsc: detached signature;
- o
- bobcat_3.23.01-x.tar.gz: source archive;
- o
- bobcat_3.23.01-x_i386.changes: change log;
- o
- libbobcat1_3.23.01-x_*.deb: debian package holding the
libraries;
- o
- libbobcat1-dev_3.23.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’.
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).