fast-factor

A fast integer factorisation library for unsigned integers in Rust.

Usage

Add to your Cargo.toml:

[dependencies]
fast-factor = "0.1.1"

Functions

`factor(n)`

Returns all factors of n, including 1 and n itself. Returns an empty vector for 0.

assert_eq!(fast_factor::factor(12_u32), vec![1, 2, 3, 4, 6, 12]);
assert_eq!(fast_factor::factor(1_u32),  vec![1]);
assert_eq!(fast_factor::factor(0_u32),  vec![]);

`proper_factor(n)`

Returns all factors of n, excluding n itself.

assert_eq!(fast_factor::proper_factor(12_u32), vec![1, 2, 3, 4, 6]);
assert_eq!(fast_factor::proper_factor(1_u32),  vec![]);

`exclusive_factor(n)`

Returns all factors of n, excluding both 1 and n itself.

assert_eq!(fast_factor::exclusive_factor(12_u32), vec![2, 3, 4, 6]);
assert_eq!(fast_factor::exclusive_factor(7_u32),  vec![]);

Generics

All functions are generic over any type implementing PrimInt + Unsigned + Roots, so they work with u8, u16, u32, u64, u128, and usize.

fast_factor::factor(100_u64);
fast_factor::factor(255_u8);

Algorithm

Each function finds factors up to sqrt(n) and derives the complementary factors by division, giving O(sqrt(n)) time complexity.

License

MIT

fast-factor 0.1.1