Detailed Description

Author: hacatu

Version: 0.2.0

LICENSE

This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/.

DESCRIPTION

Sieve based functions for computing primes in a range or divisor counts/ power sums/Euler's totient function/Carmichael's function on all numbers in a range. Arrays returned from sieve functions should be freed when no longer needed.

Definition in file sieves.h.

Go to the source code of this file.

Functions
NUT_ATTR_CONST uint64_t	nut_max_prime_divs (uint64_t max)
	Compute the maximum number of unique prime divisors a number can have.

NUT_ATTR_CONST uint64_t	nut_max_primes_le (uint64_t max)
	Compute an upper bound on the number of primes up to max.

bool	nut_u64_make_factorial_tbl (uint64_t k, uint64_t modulus, uint64_t bits, uint64_t max_denom, uint64_t factorials[static bits+k], uint64_t inv_factorials[static max_denom+1])
	Calculate factorials and inverse factorials for a given upper bound and modulus.

NUT_ATTR_MALLOC void *	nut_sieve_factorizations (uint64_t max, uint64_t *_w)
	Compute the factorization for every number in the range from 0 to max.

NUT_ATTR_CONST uint64_t	nut_get_factorizations_pitch (uint64_t w)
	Get the pitch for a pitched array of factorization structs with w unique prime divisors.

NUT_ATTR_MALLOC void *	nut_sieve_factors (uint64_t max, uint64_t *_w)
	Compute the unique prime factors of every number in the range from 0 to max.

NUT_ATTR_MALLOC uint8_t *	nut_sieve_omega (uint64_t max)
	Compute the number of distinct prime divisors of every number in the range from 0 to max.

NUT_ATTR_MALLOC uint64_t *	nut_sieve_largest_factors (uint64_t max)
	Compute the largest prime factor of every number in the range from 0 to max.

void	nut_fill_factors_from_largest (nut_Factors *restrict out, uint64_t n, const uint64_t largest_factors[restrict static n+1])
	Use a table of largest prime factors to get the factorization of a number.

NUT_ATTR_MALLOC uint32_t *	nut_sieve_smallest_factors (uint64_t max)
	Compute the smallest prime factor of every number in the range from 0 to max, or 1 for primes Compared to `nut_sieve_factors`, this uses up to 60 times less memory, so if the range is very large, most numbers will never actually have their factorizations accessed, or the factorizations will only be accessed about once, this function should be preferred.

void	nut_fill_factors_from_smallest (nut_Factors *restrict out, uint64_t n, const uint32_t smallest_factors[restrict static n+1])
	Use a table of smallest prime factors to get the factorization of a number.

NUT_ATTR_CONST uint64_t	nut_get_factors_pitch (uint64_t w)
	Get the pitch for a pitched array of `nut_u64_Pitcharr` factor lists.

NUT_ATTR_MALLOC uint64_t *	nut_sieve_sigma_0 (uint64_t max)
	Compute the number of divisors (including 1 and n) for every number n from 0 to max.

NUT_ATTR_MALLOC uint64_t *	nut_sieve_sigma_1 (uint64_t max)
	Compute the sum of divisors (including 1 and n) for every number n from 0 to max.

NUT_ATTR_MALLOC uint64_t *	nut_sieve_sigma_e (uint64_t max, uint64_t e)
	Compute the sum of some power of divisors (including 1 and n) for every number n from 0 to max.

NUT_ATTR_MALLOC uint64_t *	nut_sieve_dk (uint64_t max, uint64_t k, uint64_t modulus)
	Compute the generalized divisor function dk(n) (number of k-tuples with product n) for every number n from 0 to max.

NUT_ATTR_MALLOC uint64_t *	nut_sieve_phi (uint64_t max)
	Compute Euler's totient function for every number from 0 to max.

NUT_ATTR_MALLOC uint64_t *	nut_sieve_carmichael (uint64_t max)
	Compute the Carmichael function for every number from 0 to max.

NUT_ATTR_MALLOC uint8_t *	nut_sieve_mobius (uint64_t max)
	Compute the Mobius function for every number from 0 to max.

NUT_ATTR_MALLOC int64_t *	nut_compute_mertens_range (uint64_t max, const uint8_t mobius[static max/4+1])
	Compute the Mertens function (sum of Mobius function) for every number from 0 to max.

NUT_ATTR_MALLOC uint8_t *	nut_sieve_is_composite (uint64_t max)
	Compute a bitarray of whether or not each number from 0 to max is composite.

NUT_ATTR_PURE bool	nut_is_composite (uint64_t n, const uint8_t buf[static n/30+1])
	Check if a number is composite using a packed bitarray from `nut_sieve_is_composite`.

NUT_ATTR_MALLOC uint64_t *	nut_compute_pi_range (uint64_t max, const uint8_t buf[static max/30+1])
	Compute the pi (prime counting) function for every number from 0 to max.

NUT_ATTR_PURE uint64_t	nut_compute_pi_from_tables (uint64_t n, const uint64_t pi_table[restrict static n/30], const uint8_t buf[restrict static n/30+1])
	Get the value for the pi (prime counting) function for a particular number using precomputed tables.

NUT_ATTR_MALLOC uint64_t *	nut_sieve_primes (uint64_t max, uint64_t *_num_primes)
	Compute an array of all primes from 0 to max.

Function Documentation

◆ nut_max_prime_divs()

NUT_ATTR_CONST uint64_t nut_max_prime_divs ( uint64_t max )

Compute the maximum number of unique prime divisors a number can have.

This has nothing to do with factoring the number and is just a simple binary decision diagram based on comparing the number to 2, 2*3, 2*3*5, etc.

Parameters

[in] max number to find max unique prime divisors of

Returns: the largest number of unique prime divisors any number not exceeding max can possibly have

◆ nut_max_primes_le()

NUT_ATTR_CONST uint64_t nut_max_primes_le ( uint64_t max )

Compute an upper bound on the number of primes up to max.

This uses an inequality involving log derived from the prime number theorem to always get an upper bound.

Parameters

[in]	max	number to find the number of primes up to
	an	upper bound on the number of primes up to max

◆ nut_u64_make_factorial_tbl()

bool nut_u64_make_factorial_tbl	(	uint64_t	k,
		uint64_t	modulus,
		uint64_t	bits,
		uint64_t	max_denom,
		uint64_t	factorials[static bits+k],
		uint64_t	inv_factorials[static max_denom+1]
	)

Calculate factorials and inverse factorials for a given upper bound and modulus.

Parameters

[in]	k	factorials[bits + k - 1] is the last factorial that will be computed
[in]	modulus	modulus to reduce result by. Must be large enough that all inv factorials are actually invertable
[in]	bits	used with k to find the last factorial to compute
[in]	max_denom	inv_factorials[max_denom] is the last one that will be computed
[out]	factorials	output for factorial table
[out]	inv_factorials	output for inverse factorial table

Returns: true on success, false on failure (if the inverse of some factorial can't be found)

◆ nut_sieve_factorizations()

NUT_ATTR_MALLOC void * nut_sieve_factorizations	(	uint64_t	max,
		uint64_t *	_w
	)

Compute the factorization for every number in the range from 0 to max.

The factorizations for 0 and 1 are not actually computed. The factorizations are stored in an array of factors_t structs with capacity w, where w is the maximum number of unique prime divisors of a number not exceeding max. The result is a pitched array. nut_Pitcharr_get should be used to handle the returned value. get_factorizations_pitch should be used to get the pitch from the output parameter w.

Parameters

[in]	max	inclusive upper bound of sieving range in which to factor all numbers
[out]	_w	store w, the maximum number of unique prime divisors of a number not exceeding max

Returns: a pointer to an array of factors_t structs containing the factorization of all numbers not exceeding max, or NULL on allocation failure

◆ nut_get_factorizations_pitch()

NUT_ATTR_CONST uint64_t nut_get_factorizations_pitch ( uint64_t w )

Get the pitch for a pitched array of factorization structs with w unique prime divisors.

This is simply offsetof(factors_t, factors) + w*sizeof(dummy->factors[0]), where dummy is an expression with type factors_t.

Parameters

[in] w The maximal number of unique prime divisors of any potential index of the pitched array. Should be obtained from nut_sieve_factorizations, max_prime_divisors, etc.

Returns: The pitch of a pitched array of factorization structs whose flexible length members all have w elements.

◆ nut_sieve_factors()

NUT_ATTR_MALLOC void * nut_sieve_factors	(	uint64_t	max,
		uint64_t *	_w
	)

Compute the unique prime factors of every number in the range from 0 to max.

The factors for 0 and 1 are not actually computed. The result is stored in an array of nut_u64_Pitcharr structs with capacity w, where w is the maximum number of unique prime divisors of a number not exceeding max. The pitch of the result may be obtained with get_factors_pitch. nut_Pitcharr_get should be used to handle the returned value.

Parameters

[in]	max	inclusive upper bound of sieving range in which to find unique prime factors of all numbers
[out]	_w	maximum numer of unique prime divisors of a number not exceeding max

Returns: a pointer to an array of nut_u64_Pitcharr structs containing lists of unique prime factors for all numbers not exceeding max, or NULL on allocation failure

◆ nut_sieve_omega()

NUT_ATTR_MALLOC uint8_t * nut_sieve_omega ( uint64_t max )

Compute the number of distinct prime divisors of every number in the range from 0 to max.

The divisors for 0 and 1 are not actually computed.

Parameters

[in] max inclusive upper bound of sieving range in which to find distinct prime divisor counts of all numbers

Returns: a pointer to an array of distinct prime divisor counts for all numbers not exceeding max, or NULL on allocation failure

◆ nut_sieve_largest_factors()

NUT_ATTR_MALLOC uint64_t * nut_sieve_largest_factors ( uint64_t max )

Compute the largest prime factor of every number in the range from 0 to max.

Compared to nut_sieve_factors, this uses up to 30 times less memory, so if the range is very large, most numbers will never actually have their factorizations accessed, or the factorizations will only be accessed about once, this function should be preferred. The factors of 0 and 1 are not actually computed, their entries in the returned array will be 0. You can use the resulting table as it is, or convert it to a factorization using nut_fill_factors_from_largest.

Parameters

[in] max inclusive upper bound of sieving range in which to find largest prime factors of all numbers

Returns: a pointer to an array of largest prime factors for all numbers not exceeding max, or NULL on allocation failure.

◆ nut_fill_factors_from_largest()

void nut_fill_factors_from_largest	(	nut_Factors *restrict	out,
		uint64_t	n,
		const uint64_t	largest_factors[restrict static n+1]
	)

Use a table of largest prime factors to get the factorization of a number.

Parameters

[out]	out	Factors struct to store result in. MUST be allocated already, use `nut_make_Factors_ub` or `nut_max_prime_divs` and `nut_make_Factors_w` if needed.
[in]	n	the number to get the factorization of
[in]	largest_factors	table of largest factors, from `nut_sieve_largest_factors`

◆ nut_sieve_smallest_factors()

NUT_ATTR_MALLOC uint32_t * nut_sieve_smallest_factors ( uint64_t max )

Compute the smallest prime factor of every number in the range from 0 to max, or 1 for primes Compared to nut_sieve_factors, this uses up to 60 times less memory, so if the range is very large, most numbers will never actually have their factorizations accessed, or the factorizations will only be accessed about once, this function should be preferred.

The factors of 0 and 1 are not actually computed, their entries in the returned array will be 0. You can use the resulting table as it is, or convert it to a factorization using nut_fill_factors_from_smallest. This function is able to store factors as 32 bit integers instead of 64, since the smallest prime factor of a composite number is at most its square root. This is why we store 1 for primes instead of themselves

Parameters

[in] max inclusive upper bound of sieving range in which to find smallest prime factors of all numbers

Returns: a pointer to an array of smallest prime factors for all numbers not exceeding max, or NULL on allocation failure.

◆ nut_fill_factors_from_smallest()

void nut_fill_factors_from_smallest	(	nut_Factors *restrict	out,
		uint64_t	n,
		const uint32_t	smallest_factors[restrict static n+1]
	)

Use a table of smallest prime factors to get the factorization of a number.

Parameters

[out]	out	Factors struct to store result in. MUST be allocated already, use `nut_make_Factors_ub` or `nut_max_prime_divs` and `nut_make_Factors_w` if needed.
[in]	n	the number to get the factorization of
[in]	smallest_factors	table of smallest factors, from `nut_sieve_smallest_factors`

◆ nut_get_factors_pitch()

NUT_ATTR_CONST uint64_t nut_get_factors_pitch ( uint64_t w )

Get the pitch for a pitched array of nut_u64_Pitcharr factor lists.

This is simply offsetof(nut_u64_Pitcharr, elems) + *_w*sizeof(uint64_t).

Parameters

[in] w The maximal number of unique prime divisors of any potential index of the pitched array. Should be obtained from nut_sieve_factors, max_prime_divisors, etc.

Returns: The pitch of a pitched array of factor list structs whose flexible length members all have w elements.

◆ nut_sieve_sigma_0()

NUT_ATTR_MALLOC uint64_t * nut_sieve_sigma_0 ( uint64_t max )

Compute the number of divisors (including 1 and n) for every number n from 0 to max.

The results for 0 and 1 are not actually computed. This effectively computes divisor_count for all numbers in the range, but without needing to compute or store the factorizations intermediately

Parameters

[in] max inclusive upper bound of sieving range in which to find divisor counts for all numbers

Returns: an array of divisor counts for all numbers in the range, or NULL on allocation failure

◆ nut_sieve_sigma_1()

NUT_ATTR_MALLOC uint64_t * nut_sieve_sigma_1 ( uint64_t max )

Compute the sum of divisors (including 1 and n) for every number n from 0 to max.

The results for 0 and 1 are not actually computed. This effectively computes divisor_sum for all numbers in the range, but without needing to compute or store the factorizations intermediately

Parameters

[in] max inclusive upper bound of sieving range in which to find divisor sums for all numbers

Returns: an array of divisor sums for all numbers in the range, or NULL on allocation failure

◆ nut_sieve_sigma_e()

NUT_ATTR_MALLOC uint64_t * nut_sieve_sigma_e	(	uint64_t	max,
		uint64_t	e
	)

Compute the sum of some power of divisors (including 1 and n) for every number n from 0 to max.

The results for 0 and 1 are not actually computed. This effectively computes divisor_power_sum for all numbers in the range, but without needing to compute or store the factorizations intermediately

Parameters

[in]	max	inclusive upper bound of sieving range in which to find divisor power sums for all numbers
[in]	e	power of divisors for summing, eg 0 would produce divisor counts, 1 divisor sums, 2 sums of squares of divisors, etc

Returns: an array of divisor power sums for all numbers in the range, or NULL on allocation failure

◆ nut_sieve_dk()

NUT_ATTR_MALLOC uint64_t * nut_sieve_dk	(	uint64_t	max,
		uint64_t	k,
		uint64_t	modulus
	)

Compute the generalized divisor function dk(n) (number of k-tuples with product n) for every number n from 0 to max.

The results for 0 and 1 are not actually computed. This effectively computes divisor_tuple_count for all numbers in the range, but without needing to compute or store the factorizations intermediately. Note that dk is multiplicative so dk(mn) = dk(m)dk(n) when m and n are coprime, and dk(p^a) = binom(a + k, k) for prime powers. In other words, dk is exponential in k and this function will overflow if max^k is too large.

Parameters

[in]	max	inclusive upper bound of sieving range in which to compute generalized divisor function
[in]	k	number of factors per factorization, eg for a prime power p^a we get binom(a + k, k).
[in]	modulus	modulus to reduce results by, or zero to skip reducing

Returns: an array of dk results, or NULL on allocation failure

◆ nut_sieve_phi()

NUT_ATTR_MALLOC uint64_t * nut_sieve_phi ( uint64_t max )

Compute Euler's totient function for every number from 0 to max.

The results for 0 and 1 are not actually computed. This effectively computes euler_phi for all numbers in the range, but without needing to compute or store the factorizations intermediately

Parameters

[in] max inclusive upper bound of sieving range in which to find totients for all numbers

Returns: an array of totients for all numbers in the range, or NULL on allocation failure

◆ nut_sieve_carmichael()

NUT_ATTR_MALLOC uint64_t * nut_sieve_carmichael ( uint64_t max )

Compute the Carmichael function for every number from 0 to max.

The results for 0 and 1 are not actually computed. This effectively computes carmichael_lambda for all numbers in the range, but without needing to compute or store the factorizations intermediately

Parameters

[in] max inclusive upper bound of sieving range in which to compute Carmichael for all numbers

Returns: an array of Carmichael function outputs for all numbers in the range, or NULL on allocation failure

◆ nut_sieve_mobius()

NUT_ATTR_MALLOC uint8_t * nut_sieve_mobius ( uint64_t max )

Compute the Mobius function for every number from 0 to max.

The result is stored in an array of 2 bit integers, which should be accessed by nut_Bitfield2_arr_get. That function will return 0 for 0, 1 for 1, and 3 for -1. 2 will not be stored anywhere in bounds in the resulting array.

Parameters

[in] max inclusive upper bound of sieving range in which to compute Mobius for all numbers

Returns: a bitfield array of Mobius function outputs for all numbers in the range, with 3 instead of -1, or NULL on allocation failure

◆ nut_compute_mertens_range()

NUT_ATTR_MALLOC int64_t * nut_compute_mertens_range	(	uint64_t	max,
		const uint8_t	mobius[static max/4+1]
	)

Compute the Mertens function (sum of Mobius function) for every number from 0 to max.

Note that this function is signed.

Parameters

[in]	max	inclusive upper bound of range in which to compute Mertens for all numbers
[in]	mobius	bitfield array of Mobius function outputs (from `nut_sieve_mobius`).

Returns: an array of Mertens function outputs for all numbers in the range, or NULL on allocation failure

◆ nut_sieve_is_composite()

NUT_ATTR_MALLOC uint8_t * nut_sieve_is_composite ( uint64_t max )

Compute a bitarray of whether or not each number from 0 to max is composite.

1 is composite, and 0 is considered composite here. The result should be used with nut_is_composite since it is packed (only stores bitflags for numbers coprime to 30).

Parameters

[in]	max	inclusive upper bound of sieving range in which to check compositeness for all numbers
[out]	_num_primes	the number of primes in the range will be stored here. May be NULL.

Returns: a bitarray of whether or not each number in the range is composite, or NULL on allocation failure

◆ nut_is_composite()

NUT_ATTR_PURE bool nut_is_composite	(	uint64_t	n,
		const uint8_t	buf[static n/30+1]
	)

Check if a number is composite using a packed bitarray from nut_sieve_is_composite.

Parameters

[in]	n	the number to check if composite
[in]	buf	packed bitarray from `nut_sieve_is_composite`

Returns: true if n is composite, false if n is prime

◆ nut_compute_pi_range()

NUT_ATTR_MALLOC uint64_t * nut_compute_pi_range	(	uint64_t	max,
		const uint8_t	buf[static max/30+1]
	)

Compute the pi (prime counting) function for every number from 0 to max.

The result should be used with nut_compute_pi_from_tables since pi is only actually calculated at every 240th number since intermediate results can be computed with a single popcount on the packed buf bitarray.

Parameters

[in]	max	inclusive upper bound of range to compute pi function
[in]	buf	packed bitarray from `nut_sieve_is_composite`

Returns: an array of pi values at every 240th number (use nut_compute_pi_from_tables)

◆ nut_compute_pi_from_tables()

NUT_ATTR_PURE uint64_t nut_compute_pi_from_tables	(	uint64_t	n,
		const uint64_t	pi_table[restrict static n/30],
		const uint8_t	buf[restrict static n/30+1]
	)

Get the value for the pi (prime counting) function for a particular number using precomputed tables.

Parameters

[in]	n	the number to calculate pi for
[in]	pi_table	array of partial pi values from `nut_compute_pi_range`
[in]	buf	packed bitarray from `nut_sieve_is_composite`

Returns: the number of primes <= n

◆ nut_sieve_primes()

NUT_ATTR_MALLOC uint64_t * nut_sieve_primes	(	uint64_t	max,
		uint64_t *	_num_primes
	)

Compute an array of all primes from 0 to max.

Parameters

[in]	max	inclusive upper bound of sieving range
[out]	_num_primes	how many primes were found in the range (this pointer cannot be null)

Returns: an array of all primes from 0 to max, or NULL on allocation failure

Detailed Description

LICENSE

DESCRIPTION

Functions

Function Documentation

◆ nut_max_prime_divs()

◆ nut_max_primes_le()

◆ nut_u64_make_factorial_tbl()

◆ nut_sieve_factorizations()

◆ nut_get_factorizations_pitch()

◆ nut_sieve_factors()

◆ nut_sieve_omega()

◆ nut_sieve_largest_factors()

◆ nut_fill_factors_from_largest()

◆ nut_sieve_smallest_factors()

◆ nut_fill_factors_from_smallest()

◆ nut_get_factors_pitch()

◆ nut_sieve_sigma_0()

◆ nut_sieve_sigma_1()

◆ nut_sieve_sigma_e()

◆ nut_sieve_dk()

◆ nut_sieve_phi()

◆ nut_sieve_carmichael()

◆ nut_sieve_mobius()

◆ nut_compute_mertens_range()

◆ nut_sieve_is_composite()

◆ nut_is_composite()

◆ nut_compute_pi_range()

◆ nut_compute_pi_from_tables()

◆ nut_sieve_primes()