Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

home | help
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 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.

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  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[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.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-
	      braries, 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).

libbobcat-dev_3.25.01-x.tar.gz	   2005-2015	    FBB::PrimeFactors(3bobcat)

NAME | SYNOPSIS | DESCRIPTION | NAMESPACE | INHERITS FROM | TYPEDEFS AND ENUMS | CONSTRUCTORS | OVERLOADED OPERATORS | MEMBER FUNCTION | EXAMPLE | FILES | SEE ALSO | BUGS | DISTRIBUTION FILES | BOBCAT | COPYRIGHT | AUTHOR

Want to link to this manual page? Use this URL:
<https://www.freebsd.org/cgi/man.cgi?query=primefactors&sektion=3bobcat&manpath=FreeBSD+12.1-RELEASE+and+Ports>

home | help