FBB::PrimeFactors(3bobcat)

📦
version 6.15.01 · 7 versions
, in ubuntu stonking

💖 NAME 💖

FBB::PrimeFactors — bestie, this class does the prime-number factorization of (BigInt) values. That's the whole gig. 🧚✨

📜 SYNOPSIS 📜

#include <bobcat/primefactors>

Linking option: -lbobcat

🌸 DESCRIPTION 🌸

okay so. Integral values come in two flavors, and no there is no third one:

  • prime numbers — their only integral divisors are their own values and 1
  • composite numbers — these also have at least one other (prime number) integral divisor

And every single composite integral value can be factorized as the product of prime numbers. Like, 6 factorizes as 2 * 3, and 8 factorizes as 2 * 2 * 2. Finding those is called the prime number factorization, or prime factorization (iykyk). 💅

When you factorize a value, its prime factors may sometimes get used repeatedly 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. Here's the tea: when factorizing a value, prime numbers up to sqrt(value) must be available, because prime numbers up to sqrt(value) may be factors of value. Right now PrimeFactors uses the sieve of Eratosthenes to find those 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. And once they're determined, those prime numbers may again be used when factorizing the next integral value. iconic behavior honestly. 🎀

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. no cap.

👑 INHERITS FROM 👑

-

(nothing, she's self-made, main character energy 💅)

✨ TYPEDEFS AND ENUMS ✨

  • 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. 🔥

  • Factors — is a synonym for std::vector<PrimePower

🛠 CONSTRUCTORS 🛠

  • 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. sharing is caring fr fr 🫶

  • 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. slay ✅
  • 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. besties sharing a closet basically 👯‍♀️

🌈 MEMBER FUNCTION 🌈

  • 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

periodt. 💅✨

📁 FILES 📁

  • bobcat/primefactors — defines the class interface

👀 SEE ALSO 👀

bobcat(7), bigint(3bobcat)

💀 BUGS 💀

None Reported.

(not a single one. we love a clean queen 👑)

🎀 BOBCAT PROJECT FILES 🎀

Debian Bobcat project files:

  • libbobcat6: debian package containing the shared library, changelog and copyright note;
  • libbobcat-dev: debian package containing the static library, headers, manual pages, and developer info;

🐱 BOBCAT 🐱

Bobcat is an acronym of Brokken’s Own Base Classes And Templates. say it with me now 🗣

This is free software, distributed under the terms of the GNU General Public License (GPL). 💜

💖 AUTHOR 💖

Frank B. Brokken (f.b.brokken@rug.nl).

and that's a wrap bestie 🫶 this whole page came to you from libbobcat-dev_6.15.01, dated 2005-2026, and it lives under the name FBB::PrimeFactors(3bobcat). go forth and factorize, you absolute icon 🌸🦋💅

📦 where this page comes from