Struct LinearSieve

pub struct LinearSieve<const LEN: usize> { /* private fields */ }

Generate a table of prime numbers by linear sieving.

This structure supports table generation by compile-time calculations and can also determine prime numbers at compile time.

Limitations

The range generated is 0..LEN, NOT 0..=LEN. This is due to the limitations of the const generics.
Therefore, even if memory and computation time were infinite, this structure could not be used to determine whether usize::MAX is prime or not.

Also, implementation of types other than usize is currently not provided.
It may be possible to implement it through specialization or const_trait_impl stabilization, but no implementation method has been found so far.

Examples

use primality_test::LinearSieve;

const S: LinearSieve<15> = LinearSieve::new();
const PRIME: bool = S.is_prime(7);
const NOT_PRIME: bool = S.is_prime(10);

assert!(PRIME);
assert!(!NOT_PRIME);

Note that [T; N] is used instead of Vec<T> to support compile-time calculations.
This may result in increased stack memory usage for runtime table generation.

use primality_test::LinearSieve;

// Data size is too big...
// At this line, stack overflow may occur.
let _s = LinearSieve::<10000000000000>::new();

Implementations

impl<const LEN: usize> LinearSieve<LEN>

pub const fn new() -> Self

Constructor.
This method supports the compile-time generation.

pub const fn len(&self) -> usize

Return the length of the internal array.

The value returned by this method is always equal to LEN.

pub const fn is_prime(&self, value: usize) -> bool

Check if value is prime or not.

Panics

This method panics when value >= LEN is true.

Examples

use primality_test::LinearSieve;

const S: LinearSieve<1000> = LinearSieve::new();
assert!(S.is_prime(2));
assert!(S.is_prime(997));

assert!(!S.is_prime(0));
assert!(!S.is_prime(1));
assert!(!S.is_prime(561));
// S.is_prime(1000)     // Panic at this line

pub fn factors(&self, value: usize) -> impl Iterator<Item = usize> + '_

Factorize value into prime factors.

LinearSieve keeps internally the least prime factor of each value.
By using this, the method is guaranteed to return the prime factors of value in ascending order.

1 is not contained in the returned factors.
If value is less then 2, the length of returned iterator is always 0.

Panics

This method panics when value >= LEN is true.

Examples

use primality_test::LinearSieve;

const S: LinearSieve<100> = LinearSieve::new();
let factors_of_120 = S.factors(60).collect::<Vec<_>>();
assert_eq!(factors_of_120, vec![2, 2, 3, 5]);

let factors_of_11 = S.factors(11).collect::<Vec<_>>();
assert_eq!(factors_of_11, vec![11]);

assert!(S.factors(1).next().is_none());

Trait Implementations

impl<const LEN: usize> Clone for LinearSieve<LEN>

fn clone(&self) -> LinearSieve<LEN>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<const LEN: usize> Debug for LinearSieve<LEN>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<const LEN: usize> Default for LinearSieve<LEN>

fn default() -> Self

Returns the “default value” for a type.

impl<const LEN: usize> IntoIterator for LinearSieve<LEN>

fn into_iter(self) -> Self::IntoIter

Generate a stream of prime numbers.

type Item = usize

The type of the elements being iterated over.

type IntoIter = FilterMap<Enumerate<IntoIter<usize, LEN>>, fn((usize, usize)) -> Option<usize>>

Which kind of iterator are we turning this into?

impl<const LEN: usize> Copy for LinearSieve<LEN>