malachite_base/num/factorization/
mod.rs

1// Copyright © 2026 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9/// [`Factor`](traits::Factor), a trait for computing the prime factorization of a number.
10pub mod factor;
11/// [`IsPower`](traits::IsPower) and [`ExpressAsPower`](traits::ExpressAsPower), traits for testing
12/// if a number is a perfect power and, if it is, expressing it as such.
13///
14/// # is_power
15/// ```
16/// use malachite_base::num::factorization::traits::IsPower;
17///
18/// assert!(0u8.is_power());
19/// assert!(1u16.is_power());
20/// assert!(36u32.is_power());
21/// assert!(64u32.is_power());
22/// assert!(100u64.is_power());
23/// assert!(1728u64.is_power());
24///
25/// assert!(0u8.is_power());
26/// assert!(1u16.is_power());
27/// assert!(!2u64.is_power());
28/// assert!(!3u64.is_power());
29/// ```
30///
31/// # express_as_power
32/// ```
33/// use malachite_base::num::factorization::traits::ExpressAsPower;
34///
35/// assert_eq!(0u8.express_as_power().unwrap(), (0, 2));
36/// assert_eq!(1u16.express_as_power().unwrap(), (1, 2));
37/// assert_eq!(36u32.express_as_power().unwrap(), (6, 2));
38/// assert_eq!(64u32.express_as_power().unwrap(), (2, 6));
39/// assert_eq!(100u64.express_as_power().unwrap(), (10, 2));
40/// assert_eq!(1728u64.express_as_power().unwrap(), (12, 3));
41///
42/// assert!(0u8.express_as_power().is_some());
43/// assert!(1u16.express_as_power().is_some());
44/// assert!(2u64.express_as_power().is_none());
45/// assert!(3u64.express_as_power().is_none());
46/// ```
47pub mod is_power;
48/// [`IsPrime`](traits::IsPrime), a trait for testing a number for primality.
49pub mod is_prime;
50/// [`IsSquare`](traits::IsSquare), a trait for testing if a number if a perfect square.
51///
52/// # is_square
53/// ```
54/// use malachite_base::num::factorization::traits::IsSquare;
55///
56/// assert!(0u8.is_square());
57/// assert!(1u16.is_square());
58/// assert!(4u32.is_square());
59/// assert!(256u64.is_square());
60///
61/// assert!(!2u8.is_square());
62/// assert!(!5u16.is_square());
63/// assert!(!8u32.is_square());
64/// assert!(!128u64.is_square());
65/// ```
66pub mod is_square;
67/// An efficient prime sieve.
68pub mod prime_sieve;
69/// [`Primes`](traits::Primes), a trait for generating prime numbers.
70///
71/// # primes_less_than
72/// ```
73/// use itertools::Itertools;
74/// use malachite_base::num::factorization::traits::Primes;
75///
76/// assert_eq!(u8::primes_less_than(&10).collect_vec(), &[2, 3, 5, 7]);
77/// assert_eq!(u16::primes_less_than(&11).collect_vec(), &[2, 3, 5, 7]);
78/// assert_eq!(
79///     u32::primes_less_than(&100).collect_vec(),
80///     &[
81///         2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
82///         89, 97
83///     ]
84/// );
85/// ```
86///
87/// # primes_less_than_or_equal_to
88/// ```
89/// use itertools::Itertools;
90/// use malachite_base::num::factorization::traits::Primes;
91///
92/// assert_eq!(
93///     u8::primes_less_than_or_equal_to(&10).collect_vec(),
94///     &[2, 3, 5, 7]
95/// );
96/// assert_eq!(
97///     u16::primes_less_than_or_equal_to(&11).collect_vec(),
98///     &[2, 3, 5, 7, 11]
99/// );
100/// assert_eq!(
101///     u32::primes_less_than_or_equal_to(&100).collect_vec(),
102///     &[
103///         2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
104///         89, 97
105///     ]
106/// );
107/// ```
108///
109/// # primes
110/// ```
111/// use itertools::Itertools;
112/// use malachite_base::num::factorization::traits::Primes;
113///
114/// assert_eq!(
115///     u8::primes().collect_vec(),
116///     &[
117///         2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
118///         89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179,
119///         181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251
120///     ]
121/// );
122/// ```
123pub mod primes;
124/// [`PrimitiveRootPrime`](traits::PrimitiveRootPrime), a trait for finding a primitive root modulo
125/// a prime number.
126///
127/// # primitive_root_prime
128/// ```
129/// use malachite_base::num::factorization::traits::PrimitiveRootPrime;
130///
131/// assert_eq!(5u32.primitive_root_prime(), 2);
132/// assert_eq!(191u32.primitive_root_prime(), 19);
133/// assert_eq!(4294967291u32.primitive_root_prime(), 2);
134/// ```
135pub mod primitive_root_prime;
136/// Various traits for generating primes, primality testing, and factorization.
137pub mod traits;
malachite_base/num/factorization/mod.rs

malachite_base/num/factorization/
mod.rs
