2. Primes - AparaV/math-functions GitHub Wiki

The namespace Primes contains the following functions

• primeList
• primeSieve
• isPrime
• greatestPrimeFactor
• findPrime
• countPrimeFactors
• primeFactors

Returns a int64_t array of int64_t (64 bit integers) containing prime numbers lesser than or equal to the upperLimit that is being passed into it. The end of the array is signaled by the presence of -1. This function use of the Sieve of Eratosthenes.

Parameters:
int64_t upperLimit - The upper limit for primes

Return value:
int64_t* - An array of prime numbers. Array terminates with a -1

Sample usage (after including header file):

int64_t* primes = Primes::primeList(10);
//Returns a vector {2, 3, 5, 7, -1}

Returns a bool array where the bool value at each index i corresponds to whether i is a prime (bool[i] == 1) or not (bool[i] == 0). The size of array is defined the parameter size. This makes use of the Sieve of Eratosthenes.

Parameters:
int64_t size - The upper limit of bool array

Return value:
bool* - A dynamically allocated bool array containing the sieve of Eratosthenes. This includes index 0.

Sample usage (after including header file):

bool* primes = Primes::primeSieve(10); //creates a bool array of size 10 + 1 = 11
//Returns a bool array {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0}

Returns a bool value corresponding to whether the parameter passed is prime or not.

Parameters:
int64_t n - The number to be tested for primality

Return value:
bool - 1 if prime. 0 otherwise

Sample usage (after including header file):

bool a = Primes::isPrime(3); //returns 1
bool b = Primes::isPrime(33); //returns 0

Returns the largest prime factor of a number.

Parameters:
int64_t num - The number whose largest prime factor is to be found

Return value:
int64_t - The largest prime factor of num

Sample usage (after including header file):

int64_t x = Primes::greatestPrimeFactor(10);
int64_t y = Primes::greatestPrimeFactor(5);
//x = 5
//y = 5

Returns the nth prime number.

Parameters:
int64_t n - The nth prime to be found

Return value:
int64_t - The nth prime

Sample usage (after including header file):

int64_t x = Primes::findPrime(4);
int64_t y = Primes::findPrime(5);
//x = 7
//y = 11

Finds the number of prime factors a number has.

Parameters:
int64_t num - The number whose prime factor count is to be found

Return value:
int64_t - The number of prime factors of num

Sample usage (after including header file):

int64_t x = Primes::countPrimeFactors(10);
int64_t y = Primes::countPrimeFactors(5);
//x = 2
//y = 1

Returns a std::map with the prime factorization of the number

Parameters:
int64_t num - The number that you want to prime factorize

Return value:
std::map<int, int> - A map of the prime factors of num. The key is the prime factor and the value is the exponent

Sample usage (after including header file):

map<int, int> x = Primes::primeFactors(100);
// {2:2, 5:2} ~ 100 = 2^2 * 5^2