# FreeBSD Manual Pages

FBB::PrimeFactors(3bobcat) Prime Factorization FBB::PrimeFactors(3bobcat)NAMEFBB::PrimeFactors - Performs the prime-number factorization of (BigInt) valuesSYNOPSIS#include<bobcat/primefactors> Linking option:-lbobcatDESCRIPTIONIntegral 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 aspow(2,3), and 36 is factorized as 36 = pow(2, 2) * pow(3, 2) The classFBB::PrimeFactorsperforms prime number factorizations ofFBB::BigIntvalues. When factorizing a value prime numbers up tosqrt(value)must be available, as prime numbers up tosqrt(value)may be factors ofvalue. CurrentlyPrimeFactorsuses the sieve of Eratos- thenes to find these prime numbers. To find the next prime number be- yondlastPrime, the sieve of Eratosthenes must be used repeatedly forlastPrime+=2untillastPrimeis 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 sievePrimeFactorssaves all its computed prime num- bers in either astd::vectoror 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.NAMESPACEFBBAll constructors, members, operators and manipulators, mentioned in this man-page, are defined in the namespaceFBB.INHERITS FROM-TYPEDEFS AND ENUMSostructPrimePower: contains two fields: struct PrimePower { BigInt prime; size_t power; }; Here,powerrepresents the number of timesprimecan be used as an integral divisor of the value that was factorized byPrime-Factors. oFactors: is a synonym forstd::vector_PrimePowerCONSTRUCTORSoPrimeFactors(BigIntVector&primes): Prime numbers that were determined while factorizing values are collected in theBigIntVectorthat is passed as argument to this constructor. Initially theBigIntVectorpassed as argument may be empty or may contain at least two primes (which must be, respectively, 2 and 3). The prime numbers inprimesmust be sorted. The con- structor does not verify whether the prime numbers are actually sorted, but if theBigIntVectorcontains primes itdoescheck whether the first two prime numbers are indeed 2 and 3. AnFBB::Exceptionis thrown if this condition is not met. While numbers are being factorized, new prime numbers may be added toprimes, andprimescan be reused by othherPrimeFactorsobjects. oPrimeFactors(std::stringconst&name="~/.primes",size_tblockSize=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~/.primesis used. Ifnamestarts with `~/', then this string is replaced by the user's home directory. Primes are read from the named stream in blocks of at mostblockSize, and new primes are flushed to this stream onceblock-Sizenew primes have been generated or when thePrimeFactorsob- ject (i.e., the lastPrimeFactorsobject sharing the stream) ceases to exist. If the stream does not yet exist it is created byPrimeFactors. The stream may either be empty, or it must contain sorted and white-space delimited prime numbers (inserted as hexadecimalBigIntvalues). 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 itdoescheck whether the first two prime numbers are in- deed 2 and 3. AnFBB::Exceptionis 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 otherPrimeFactorsobjects. The default copy and move constructors are available.FBB::PrimeFactorobjects created using the copy constructor share the prime numbers storage device (theBigIntVectoror the stream containing the primes) with their source objects.OVERLOADED OPERATORSThe default copy and move assignment operators are available. Left-hand sideFBB::PrimeFactorobjects receiving values from right-hand sideFBB::PrimeFactorobjects using the copy assignment operator share the prime numbers storage device (theBigIntVectoror the stream containing the primes) with their right-hand sideFBB::PrimeFactorsarguments.MEMBER FUNCTIONoFactorsconst&factorize(BigIntconst&value): The prime factors ofvalueare determined and returned in thePrimeFactors::Factorsvectors. While the prime factors ofvalueare determined new prime numbers may be added to theBigIntVec-toror to the stream that is passed to thePrimeFactorsobject. The elements ofPrimeFactors::Factorsare 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 13FILESbobcat/primefactors- defines the class interfaceSEE ALSObobcat(7),bigint(3bobcat)BUGSNone Reported.DISTRIBUTION FILESobobcat_3.25.01-x.dsc: detached signature; obobcat_3.25.01-x.tar.gz: source archive; obobcat_3.25.01-x_i386.changes: change log; olibbobcat1_3.25.01-x_*.deb: debian package holding the li- braries; olibbobcat1-dev_3.25.01-x_*.deb: debian package holding the li- braries, headers and manual pages; ohttp://sourceforge.net/projects/bobcat: public archive location;BOBCATBobcat is an acronym of `Brokken's Own Base Classes And Templates'.COPYRIGHTThis is free software, distributed under the terms of the GNU General Public License (GPL).AUTHORFrank 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>