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



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.


       Copy and move constructors (and assignment operators) are available.

       FBB::PrimeFactor objects created using the copy constructor or
       receiving their values using the copy assignment operator share the
       prime numbers storage device (the BigIntVector or the stream containing
       the primes) with their source objects.

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.

BOBCAT PROJECT FILES
       o      https://fbb-git.gitlab.io/bobcat/: gitlab project page;

       o      bobcat_6.06.02-x.dsc: detached signature;

       o      bobcat_6.06.02-x.tar.gz: source archive;

       o      bobcat_6.06.02-x_i386.changes: change log;

       o      libbobcat1_6.06.02-x_*.deb: debian package containing the
              libraries;

       o      libbobcat1-dev_6.06.02-x_*.deb: debian package containing the
              libraries, headers and manual pages;


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

libbobcat-dev_6.06.02              2005-2024        FBB::PrimeFactors(3bobcat)