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
9use crate::num::basic::integers::PrimitiveInt;
10
11// Twice the width of a `u64`, in bits (128). Shared by the double-limb square-residue mask
12// (`is_square`) and the prime sieve.
13pub(crate) const TWICE_U64_WIDTH: u64 = u64::WIDTH << 1;
14
15/// [`Factor`](traits::Factor), a trait for computing the prime factorization of a number.
16pub mod factor;
17/// [`IsPower`](traits::IsPower) and [`ExpressAsPower`](traits::ExpressAsPower), traits for testing
18/// if a number is a perfect power and, if it is, expressing it as such.
19///
20/// # is_power
21/// ```
22/// use malachite_base::num::factorization::traits::IsPower;
23///
24/// assert!(0u8.is_power());
25/// assert!(1u16.is_power());
26/// assert!(36u32.is_power());
27/// assert!(64u32.is_power());
28/// assert!(100u64.is_power());
29/// assert!(1728u64.is_power());
30///
31/// assert!(0u8.is_power());
32/// assert!(1u16.is_power());
33/// assert!(!2u64.is_power());
34/// assert!(!3u64.is_power());
35/// ```
36///
37/// # express_as_power
38/// ```
39/// use malachite_base::num::factorization::traits::ExpressAsPower;
40///
41/// assert_eq!(0u8.express_as_power().unwrap(), (0, 2));
42/// assert_eq!(1u16.express_as_power().unwrap(), (1, 2));
43/// assert_eq!(36u32.express_as_power().unwrap(), (6, 2));
44/// assert_eq!(64u32.express_as_power().unwrap(), (2, 6));
45/// assert_eq!(100u64.express_as_power().unwrap(), (10, 2));
46/// assert_eq!(1728u64.express_as_power().unwrap(), (12, 3));
47///
48/// assert!(0u8.express_as_power().is_some());
49/// assert!(1u16.express_as_power().is_some());
50/// assert!(2u64.express_as_power().is_none());
51/// assert!(3u64.express_as_power().is_none());
52/// ```
53pub mod is_power;
54/// [`IsPrime`](traits::IsPrime), a trait for testing a number for primality.
55pub mod is_prime;
56/// [`IsSquare`](traits::IsSquare), a trait for testing if a number if a perfect square.
57///
58/// # is_square
59/// ```
60/// use malachite_base::num::factorization::traits::IsSquare;
61///
62/// assert!(0u8.is_square());
63/// assert!(1u16.is_square());
64/// assert!(4u32.is_square());
65/// assert!(256u64.is_square());
66///
67/// assert!(!2u8.is_square());
68/// assert!(!5u16.is_square());
69/// assert!(!8u32.is_square());
70/// assert!(!128u64.is_square());
71/// ```
72pub mod is_square;
73/// An efficient prime sieve.
74pub mod prime_sieve;
75/// [`Primes`](traits::Primes), a trait for generating prime numbers.
76///
77/// # primes_less_than
78/// ```
79/// use itertools::Itertools;
80/// use malachite_base::num::factorization::traits::Primes;
81///
82/// assert_eq!(u8::primes_less_than(&10).collect_vec(), &[2, 3, 5, 7]);
83/// assert_eq!(u16::primes_less_than(&11).collect_vec(), &[2, 3, 5, 7]);
84/// assert_eq!(
85///     u32::primes_less_than(&100).collect_vec(),
86///     &[
87///         2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
88///         89, 97
89///     ]
90/// );
91/// ```
92///
93/// # primes_less_than_or_equal_to
94/// ```
95/// use itertools::Itertools;
96/// use malachite_base::num::factorization::traits::Primes;
97///
98/// assert_eq!(
99///     u8::primes_less_than_or_equal_to(&10).collect_vec(),
100///     &[2, 3, 5, 7]
101/// );
102/// assert_eq!(
103///     u16::primes_less_than_or_equal_to(&11).collect_vec(),
104///     &[2, 3, 5, 7, 11]
105/// );
106/// assert_eq!(
107///     u32::primes_less_than_or_equal_to(&100).collect_vec(),
108///     &[
109///         2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
110///         89, 97
111///     ]
112/// );
113/// ```
114///
115/// # primes
116/// ```
117/// use itertools::Itertools;
118/// use malachite_base::num::factorization::traits::Primes;
119///
120/// assert_eq!(
121///     u8::primes().collect_vec(),
122///     &[
123///         2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
124///         89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179,
125///         181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251
126///     ]
127/// );
128/// ```
129pub mod primes;
130/// [`PrimitiveRootPrime`](traits::PrimitiveRootPrime), a trait for finding a primitive root modulo
131/// a prime number.
132///
133/// # primitive_root_prime
134/// ```
135/// use malachite_base::num::factorization::traits::PrimitiveRootPrime;
136///
137/// assert_eq!(5u32.primitive_root_prime(), 2);
138/// assert_eq!(191u32.primitive_root_prime(), 19);
139/// assert_eq!(4294967291u32.primitive_root_prime(), 2);
140/// ```
141pub mod primitive_root_prime;
142/// Various traits for generating primes, primality testing, and factorization.
143pub mod traits;
malachite_base/num/factorization/mod.rs

malachite_base/num/factorization/
mod.rs
