Module num_prime::nt_funcs

Standalone number theoretic functions

The functions in this module can be called without an instance of crate::traits::PrimeBuffer. However, some functions do internally call the implementation on PrimeBufferExt (especially those dependent of integer factorization). For these functions, if you have to call them repeatedly, it’s recommended to create a crate::traits::PrimeBuffer instance and use its associated methods for better performance.

For number theoretic functions that depends on integer factorization, strongest primality check will be used in factorization, since for these functions we prefer correctness over speed.

Functions

• factorize
  Infaillible factorization
• factorize64
  Fast integer factorization on a u64 target. It’s based on a selection of factorization methods. if target is larger than 2^128 or more controlled primality tests are desired, please use factors().
• factorize128
  Fast integer factorization on a u128 target. It’s based on a selection of factorization methods. if target is larger than 2^128 or more controlled primality tests are desired, please use factors().
• factors
  Faillible factorization
• is_prime
  Primality test
• is_prime64
  Very fast primality test on a u64 integer is a prime number. It’s based on deterministic Miller-rabin tests with hashing. if target is larger than 2^64 or more controlled primality tests are desired, please use is_prime()
• is_safe_prime
  Test if the target is a safe prime under Sophie German’s definition. It will use the strict primality test configuration.
• is_square_free
  Tests if the integer doesn’t have any square number factor.
• moebius
  This function calculate the Möbius μ(n) function of the input integer n
• moebius_factorized
  This function calculate the Möbius μ(n) function given the factorization result of n
• next_prime
  Find the first prime number larger than target. If the result causes an overflow, then None will be returned
• nprimes
  Get the first n primes
• nth_prime
  Get the n-th prime (n counts from 1).
• nth_prime_bounds
  Returns the estimated inclusive bounds (low, high) of the n-th prime. If the result is larger than maximum of T, None will be returned.
• nth_prime_est
  Estimate the value of nth prime by bisecting on prime_pi_est. If the result is larger than maximum of T, None will be returned.
• prev_prime
  Find the first prime number smaller than target. If target is less than 3, then None will be returned.
• prime_pi
  Calculate and return the prime π function
• prime_pi_bounds
  Returns the estimated bounds (low, high) of prime π function, such that low <= π(target) <= high
• prime_pi_est
  Estimate the value of prime π() function by Riemann’s R function. The estimation error is roughly of scale O(sqrt(x)log(x)).
• primes
  Get a list of primes under a limit
• primorial
  Calculate the primorial function