Struct PrimeTable

pub struct PrimeTable { /* private fields */ }

Implementations

impl PrimeTable

pub fn new(max_n: u32) -> Self

pub fn is_prime(&self, n: u32) -> bool

pub fn primes(&self) -> impl Iterator<Item = u32> + '_

pub fn trial_division<F>(&self, n: u32, f: F)

where F: FnMut(u32, u32),

Examples found in repository

crates/competitive/src/math/prime_table.rs (line 68)

    pub fn prime_factors(&self, n: u32) -> Vec<(u32, u32)> {
        let mut factors = vec![];
        self.trial_division(n, |p, c| factors.push((p, c)));
        factors
    }
    pub fn count_divisors(&self, n: u32) -> u32 {
        let mut divisor_cnt = 1;
        self.trial_division(n, |_, cnt| divisor_cnt *= cnt + 1);
        divisor_cnt
    }
    pub fn divisors(&self, n: u32) -> Vec<u32> {
        let mut d = vec![1u32];
        self.trial_division(n, |p, c| {
            let k = d.len();
            let mut acc = 1;
            for _ in 0..c {
                acc *= p;
                for i in 0..k {
                    d.push(d[i] * acc);
                }
            }
        });
        d.sort_unstable();
        d
    }

pub fn prime_factors(&self, n: u32) -> Vec<(u32, u32)>

pub fn count_divisors(&self, n: u32) -> u32

pub fn divisors(&self, n: u32) -> Vec<u32>

Trait Implementations

impl Clone for PrimeTable

fn clone(&self) -> PrimeTable

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for PrimeTable

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

Formats the value using the given formatter.