### 17 releases

0.4.4 | May 6, 2024 |
---|---|

0.4.3 | Dec 23, 2022 |

0.4.2 | Oct 10, 2022 |

0.4.1 | May 24, 2022 |

0.3.0-alpha | Mar 3, 2022 |

#**88** in Math

**57,372** downloads per month

Used in **15** crates

**Apache-2.0**

440KB

7K
SLoC

# num-prime

This crate provides utilities for prime number related functionalities:

- Primality testing
- Deterministic primality check of

integers (using a very fast hashing algorithm)`u64` - Fermat probable prime test
- Miller-rabin probable prime test
- (strong/extra strong) Lucas probable prime test
- Baillie-PSW test
- Sophie Germain safe prime test

- Deterministic primality check of
- Primes generation and indexing
- A naive implementation of the sieve of Eratosthenes
- Unified API to support other prime generation backends
- Generate random (safe) primes
- Find previous/next prime

- Integer factorization
- Trial division
- Pollard's rho algorithm
- Shanks's square forms factorization (SQUFOF)
- Fast factorization of

and`u64`

integers`u128`

- Number theoretic functions
- Prime Pi function (number of primes under limit), its estimation and its bounds
- Nth prime, its estimation and its bounds
- Moebius function
- Divisor Sigma function
*(in examples)* - Prime Omega function
*(in examples)*

It's based on the

creates and most functions are decently optimized with pre-computed tables (see `num`**benchmark results here**).

#### Dependencies

~3.5MB

~64K SLoC