Решение задачи №81 от UniLecs с блэкджеком и модулями

prime_factorization_pretty.rs

#![deny(overflowing_literals)]

#[macro_use]
extern crate lazy_static;

const BOUND: usize = 1_000;
const IS_PRIME_SIZE: usize = BOUND - 2 + 1;

lazy_static! {
    static ref IS_PRIME: [bool; IS_PRIME_SIZE] = make_is_prime();
    static ref PRIMES: Box<[usize]> = make_primes();
}

fn make_is_prime() -> [bool; IS_PRIME_SIZE] {
    let mut is_prime = [false; IS_PRIME_SIZE];
    is_prime[0] = true;
    
    for num in (3..IS_PRIME_SIZE).filter(|&x| x % 2 != 0) {
        is_prime[num-2] = is_prime[0..num-2]
            .iter()
            .zip(2..)
            .filter(|&(&x, _)| x)
            .all(|(_, i)| num % i != 0)
    }
    
    is_prime
}

fn make_primes() -> Box<[usize]> {
    IS_PRIME.iter()
        .zip(2..)
        .filter(|&(&elem, _)| elem)
        .map(|(_, i)| i)
        .collect::<Vec<_>>()
        .into_boxed_slice()
}

fn is_prime(x: usize) -> bool {
    match x {
        0 | 1 => false,
        _other => IS_PRIME[x-2],
    }
}

mod decomposition {
    use ::std::collections::BTreeMap;
    use ::std::convert::From;
    use ::std::ops::MulAssign;
    use ::std::fmt;
    use ::std::fmt::{Display, Formatter};
    
    #[derive(PartialEq, Debug)]
    pub struct Decomposition(BTreeMap<usize, usize>);
    
    impl Decomposition {
        pub fn new() -> Self {
            Decomposition(BTreeMap::new())
        }
    }
    
    impl From<Vec<(usize, usize)>> for Decomposition {
        fn from(arg: Vec<(usize, usize)>) -> Self {
            Decomposition(arg.into_iter().collect())
        }
    }
    
    impl From<(usize, usize)> for Decomposition {
        fn from(arg: (usize, usize)) -> Self {
            let mut buf = ::std::collections::BTreeMap::new();
            buf.insert(arg.0, arg.1);
            Decomposition(buf)
        }
    }
    
    impl MulAssign<(usize, usize)> for Decomposition {
        fn mul_assign(&mut self, (prime, power): (usize, usize)) {
            let key = self.0.entry(prime).or_insert(0);
            *key += power;
        }
    }
    
    impl Display for Decomposition {
        fn fmt(&self, f: &mut Formatter) -> fmt::Result {
            let mut display = String::new();
            for (i, (&prime, &power)) in self.0.iter().enumerate() {
                if i != 0 {
                    display += " * ";
                }
                display += &prime.to_string();
                if power != 1 {
                    display += "^";
                    display += &power.to_string();
                }
            }
            f.write_str(&display)
        }
    }
}

#[derive(PartialEq, Debug)]
enum FactorizeErr {
    Zero,
    One,
    OutOfBound,
}

use decomposition::Decomposition;

fn prime_factorize(x: usize) -> Result<Decomposition, FactorizeErr> {
    use FactorizeErr::*;
    
    if x == 0 { return Err(Zero) }
    if x == 1 { return Err(One) }
    if x > BOUND { return Err(OutOfBound) }
    
    if is_prime(x) { return Ok((x, 1).into()) }
    
    let mut x = x;
    let mut decompose = Decomposition::new();
    let mut primes = PRIMES.iter().cloned();

    while x != 1 {
        let prime = primes.next().unwrap();
        let mut power = 0;
        while x % prime == 0 {
            x /= prime;
            power += 1;
        }
        if power != 0 {
            decompose *= (prime, power);
        }
    }
    
    Ok(decompose)
}

#[test]
fn check_primes() {
    for i in 2..BOUND+1 {
        if is_prime(i) {
            assert_eq!(prime_factorize(i), Ok((i, 1).into()));
        }
    }
}

#[test]
fn some_variants() {
    assert_eq!(prime_factorize(525), Ok(vec![(3, 1), (5, 2), (7, 1)].into()));
    assert_eq!(format!("{}", prime_factorize(525).unwrap()), "3 * 5^2 * 7");
    
    assert_eq!(prime_factorize(366), Ok(vec![(2, 1), (3, 1), (61, 1)].into()));
    assert_eq!(format!("{}", prime_factorize(366).unwrap()), "2 * 3 * 61");
    
    assert_eq!(prime_factorize(199), Ok((199, 1).into()));
    assert_eq!(format!("{}", prime_factorize(199).unwrap()), "199");
}

#[test]
fn check_errors() {
    use FactorizeErr::*;
    
    assert_eq!(prime_factorize(0), Err(Zero));
    assert_eq!(prime_factorize(1), Err(One));
    assert_eq!(prime_factorize(BOUND + 1), Err(OutOfBound));
}

Playground: https://play.rust-lang.org/?gist=14722a9262f149643bb45a9dd1d42656&version=stable