Решение задачи №81 от UniLecs

prime_factorization.rs

#![deny(overflowing_literals)]

#[macro_use]
//Библиотека для ленивой инициализации. Позволяет удостовериться,
//что IS_PRIME инициализируется только один раз
extern crate lazy_static;

//Верхняя граница на входные данные
const BOUND: usize = 1_000;
const IS_PRIME_SIZE: usize = BOUND - 2 + 1;

//Элемент IS_PRIME с индексом i содержит ответ на вопрос
//"является ли i+2 простым". Память под числа 0 и 1 не выделяется.
//Массив PRIMES содержит простые числа.
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; //2 -- простое число
    
    //Для всех нечётных чисел от 3 до IS_PRIME_SIZE
    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) //отбираем все простые до num
            .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()
}

//Проверяет, является ли число простым, используя IS_PRIME
fn is_prime(x: usize) -> bool {
    match x {
        0 | 1 => false,
        _other => IS_PRIME[x-2],
    }
}

#[derive(PartialEq, Debug)]
//Тип возможной ошибки при факторизации
enum FactorizeErr {
    Zero, //Передан ноль
    One, //Передана единица
    OutOfBound, //Передано число больше BOUND
}

//Разложение -- это вектор пар: первое число -- простой
//множитель, второе -- степень
type Decomposition = Vec<(usize, usize)>;

//Раскладывает число на простые множители
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(vec![(x, 1)]) }
    
    let mut x = x;
    let mut decompose = Vec::new();
    //Отбираем простые числа
    let mut primes = (2..).filter(|&i| is_prime(i));

    while x != 1 {
        //Получаем очередное простое число
        let prime = primes.next().unwrap();
        let mut power = 0;
        while x % prime == 0 { //Пока x делится на простое --
            x /= prime; //делим
            power += 1; //и подсчитываем число делений
        }
        if power != 0 { //Если prime входит в разложение -- 
            decompose.push((prime, power)); //добавляем
        }
    }
    
    Ok(decompose)
}

#[test]
//Проверяем, что для всех подсчитанных простых чисел
//разложение тривиально
fn check_primes() {
    for i in 2..BOUND+1 {
        if is_prime(i) {
            assert_eq!(prime_factorize(i), Ok(vec![(i, 1)]));
        }
    }
}

#[test]
fn some_variants() {
    assert_eq!(prime_factorize(525), Ok(vec![(3, 1), (5, 2), (7, 1)]));
    assert_eq!(prime_factorize(366), Ok(vec![(2, 1), (3, 1), (61, 1)]));
    assert_eq!(prime_factorize(199), Ok(vec![(199, 1)]));
}

#[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 (rev. 2): https://play.rust-lang.org/?gist=d0543e521d2c54cb2be458209c3bb02e&version=stable
Playground (rev. 4): https://play.rust-lang.org/?gist=49f81372a3f9c145dec0a4a9c2cbc6e1&version=stable