### 38 releases (7 breaking)

0.8.7 | Jun 19, 2024 |
---|---|

0.7.4 | May 31, 2024 |

0.4.8 | Oct 22, 2023 |

#**82** in Math

**2,372** downloads per month

**MIT/Apache**

175KB

1.5K
SLoC

# const-primes

Generate and work with prime numbers in const contexts.

This crate lets you for example pre-compute prime numbers at compile time, store them in the binary, and use them later for related computations, or check whether a number is prime in a const function.

compatible, and currently supports Rust versions 1.67.1 or newer, though enabling feature flags may increase this.`#!``[``no_std``]`

## Example: generate primes at compile time

Generate arrays of prime numbers at compile time with the function

which uses a segmented sieve of Eratosthenes:`primes`

`use` `const_primes``::`primes`;`
`const` `PRIMES``:` `[``u32``;` `10``]` `=` `primes``(``)``;`
`assert_eq!``(``PRIMES``[``5``]``,` `13``)``;`
`assert_eq!``(``PRIMES``,` `[``2``,` `3``,` `5``,` `7``,` `11``,` `13``,` `17``,` `19``,` `23``,` `29``]``)``;`

## Example: use a cache of generated primes for related computations

The struct

is a wrapper around an array of primes and can be used as a cache of prime numbers for related computations:`Primes`

`//` The first 100 primes
`const` `CACHE``:` `Primes``<`100`>` `=` `Primes``::`new`(``)``;`
`//` Primality testing
`const` `CHECK_42``:` `Option``<``bool``>` `=` `CACHE``.``is_prime``(``42``)``;`
`const` `CHECK_541``:` `Option``<``bool``>` `=` `CACHE``.``is_prime``(``541``)``;`
`assert_eq!``(``CHECK_42``,` `Some``(``false``)``)``;`
`assert_eq!``(``CHECK_541``,` `Some``(``true``)``)``;`
`//` Prime counting
`const` `PRIMES_LEQ_100``:` `Option``<``usize``>` `=` `CACHE``.``count_primes_leq``(``100``)``;`
`assert_eq!``(``PRIMES_LEQ_100``,` `Some``(``25``)``)``;`
`//` Prime factorization:
`assert_eq!``(``CACHE``.``prime_factorization``(``3072``)``.``collect``(``)``,` `&``[``(``2``,` `10``)``,` `(``3``,` `1``)``]``)`
`//` If questions are asked about numbers
`//` outside the cache it returns None
`assert!``(``CACHE``.``is_prime``(``1000``)``.``is_none``(``)``)``;`
`assert!``(``CACHE``.``count_primes_leq``(``1000``)``.``is_none``(``)``)``;`

## Example: primality checking

Use

to test whether a given number is prime:`is_prime`

`use` `const_primes``::`is_prime`;`
`const` `CHECK``:` `bool` `=` `is_prime``(``18_446_744_073_709_551_557``)``;`
`assert!``(``CHECK``)``;`

## Example: sieving

Sieve a range of numbers for their prime status with

:`sieve`

`use` `const_primes``::`sieve`;`
`const` `PRIME_STATUS``:` `[``bool``;` `10``]` `=` `sieve``(``)``;`
`//` 0 1 2 3 4 5 6 7 8 9
`assert_eq!``(``PRIME_STATUS``,` `[``false``,` `false``,` `true``,` `true``,` `false``,` `true``,` `false``,` `true``,` `false``,` `false``]``)``;`

## Example: generate the three primes after 5000000031

The crate also provides prime generation and sieving functions that can be used to work with ranges that don't start at zero, e.g.

and `primes_geq`

. These functions can use large sieves to compute large primes, but don't need to return the entire sieve, just the requested numbers.
They are most conveniently used through the macros `sieve_lt`

and `primes_segment!`

that automatically compute the size of the sieve that's needed for a certain computation.`sieve_segment!`

Compute 3 primes greater than or equal to 5000000031:

`use` `const_primes``::``{`primes_segment`,` GenerationError`}``;`
`const` N`:` `usize` `=` `3``;`
`const` `PRIMES_GEQ``:` `Result``<``[``u64``;` `N``]`, GenerationError`>` `=` `primes_segment!``(`N`;` `>=` `5_000_000_031``)``;`
`assert_eq!``(``PRIMES_GEQ``,` `Ok``(``[``5_000_000_039``,` `5_000_000_059``,` `5_000_000_063``]``)``)``;`

## Example: find the next or previous prime numbers

Find the next or previous prime numbers with

and `next_prime`

if they exist and can be represented in a `previous_prime`

:`u64`

`use` `const_primes``::``{`previous_prime`,` next_prime`}``;`
`const` `NEXT``:` `Option``<``u64``>` `=` `next_prime``(``25``)``;`
`const` `PREV``:` `Option``<``u64``>` `=` `previous_prime``(``25``)``;`
`const` `NO_SUCH``:` `Option``<``u64``>` `=` `previous_prime``(``2``)``;`
`const` `TOO_BIG``:` `Option``<``u64``>` `=` `next_prime``(``u64``::``MAX``)``;`
`assert_eq!``(``NEXT``,` `Some``(``29``)``)``;`
`assert_eq!``(``PREV``,` `Some``(``23``)``)``;`
`assert_eq!``(``NO_SUCH``,` `None``)``;`
`assert_eq!``(``TOO_BIG``,` `None``)``;`

and more!

## Feature flags

: implements the `std`

trait from the standard library for the error types.`Error`

: derives the `serde`

and `Serialize`

traits from `Deserialize`

for the `serde`

struct, as well as a few others.`Primes`

: promotes panics that only involve const generics into compile errors. Increases the MSRV of the crate to 1.79.0.`const_assert`

## License

Licensed under either of

- Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

## Contribution

Contributions are welcome!

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

#### Dependencies

~170KB