relp-num 0.1.14

Number types for the relp crate
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

use std::hint::assert_unchecked;
use std::num::NonZeroU16;

use crate::integer::factorization::prime::primes::SMALL_ODD_PRIMES_16;

pub fn factorize(value: NonZeroU16) -> Vec<(u16, u32)> {
    let mut x = value.get();
    // 2 * 3 * 5 * 7 * 11 * 13 * 17 > 2 ** 16, so six values are enough
    let mut factors = Vec::with_capacity(6);

    let two_powers = x.trailing_zeros();
    if two_powers > 0 {
        x >>= two_powers;
        factors.push((2, two_powers));
    }

    for divisor in SMALL_ODD_PRIMES_16 {
        unsafe { assert_unchecked(divisor != 0); }

        let mut count = 0;
        while x.is_multiple_of(divisor) {
            x /= divisor;
            count += 1;
        }

        if count > 0 {
            factors.push((divisor, count));
        }

        if x == 1 {
            break;
        }
    }

    if x != 1 {
        factors.push((x, 1));
    }

    factors
}