malachite_nz/natural/factorization/
primes.rs

1// Copyright © 2025 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::natural::Natural;
10use malachite_base::num::conversion::traits::SaturatingFrom;
11use malachite_base::num::factorization::primes::{PrimesIterator, PrimesLessThanIterator};
12use malachite_base::num::factorization::traits::Primes;
13
14/// An iterator over that generates all prime [`Natural`]s less than a given value.
15///
16/// This `struct` is created by [`Natural::primes_less_than`] and
17/// [`Natural::primes_less_than_or_equal_to`]; see their documentation for more.
18#[derive(Clone, Debug)]
19pub struct NaturalPrimesLessThanIterator(PrimesLessThanIterator<u64>);
20
21impl Iterator for NaturalPrimesLessThanIterator {
22    type Item = Natural;
23
24    #[inline]
25    fn next(&mut self) -> Option<Natural> {
26        self.0.next().map(Natural::from)
27    }
28}
29
30/// An iterator over that generates all prime [`Natural`]s.
31///
32/// This `struct` is created by [`Natural::primes`]; see its documentation for more.
33#[derive(Clone, Debug)]
34pub struct NaturalPrimesIterator(PrimesIterator<u64>);
35
36impl Iterator for NaturalPrimesIterator {
37    type Item = Natural;
38
39    #[inline]
40    fn next(&mut self) -> Option<Natural> {
41        self.0.next().map(Natural::from)
42    }
43}
44
45impl Primes for Natural {
46    type I = NaturalPrimesIterator;
47    type LI = NaturalPrimesLessThanIterator;
48
49    /// Returns an iterator that generates all primes less than a given value.
50    ///
51    /// The iterator produced by `primes_less_than(n)` generates the same primes as the iterator
52    /// produced by `primes().take_while(|&p| p < n)`, but the latter would be slower because it
53    /// doesn't know in advance how large its prime sieve should be, and might have to create larger
54    /// and larger prime sieves.
55    ///
56    /// # Worst-case complexity (amortized)
57    /// $T(i) = O(\log \log i)$
58    ///
59    /// $M(i) = O(1)$
60    ///
61    /// where $T$ is time, $M$ is additional memory, and $i$ is the iteration index.
62    ///
63    /// # Examples
64    /// ```
65    /// use itertools::Itertools;
66    /// use malachite_base::num::factorization::traits::Primes;
67    /// use malachite_base::strings::ToDebugString;
68    /// use malachite_nz::natural::Natural;
69    ///
70    /// assert_eq!(
71    ///     Natural::primes_less_than(&Natural::from(10u32))
72    ///         .collect_vec()
73    ///         .to_debug_string(),
74    ///     "[2, 3, 5, 7]"
75    /// );
76    /// assert_eq!(
77    ///     Natural::primes_less_than(&Natural::from(11u32))
78    ///         .collect_vec()
79    ///         .to_debug_string(),
80    ///     "[2, 3, 5, 7]"
81    /// );
82    /// assert_eq!(
83    ///     Natural::primes_less_than(&Natural::from(100u32))
84    ///         .collect_vec()
85    ///         .to_debug_string(),
86    ///     "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, \
87    ///     83, 89, 97]"
88    /// );
89    /// ```
90    #[inline]
91    fn primes_less_than(n: &Natural) -> NaturalPrimesLessThanIterator {
92        NaturalPrimesLessThanIterator(u64::primes_less_than(&u64::saturating_from(n)))
93    }
94
95    /// Returns an iterator that generates all primes less than or equal to a given value.
96    ///
97    /// The iterator produced by `primes_less_than_or_equal_to(n)` generates the same primes as the
98    /// iterator produced by `primes().take_while(|&p| p <= n)`, but the latter would be slower
99    /// because it doesn't know in advance how large its prime sieve should be, and might have to
100    /// create larger and larger prime sieves.
101    ///
102    /// # Worst-case complexity (amortized)
103    /// $T(i) = O(\log \log i)$
104    ///
105    /// $M(i) = O(1)$
106    ///
107    /// where $T$ is time, $M$ is additional memory, and $i$ is the iteration index.
108    ///
109    /// # Examples
110    /// ```
111    /// use itertools::Itertools;
112    /// use malachite_base::num::factorization::traits::Primes;
113    /// use malachite_base::strings::ToDebugString;
114    /// use malachite_nz::natural::Natural;
115    ///
116    /// assert_eq!(
117    ///     Natural::primes_less_than_or_equal_to(&Natural::from(10u32))
118    ///         .collect_vec()
119    ///         .to_debug_string(),
120    ///     "[2, 3, 5, 7]"
121    /// );
122    /// assert_eq!(
123    ///     Natural::primes_less_than_or_equal_to(&Natural::from(11u32))
124    ///         .collect_vec()
125    ///         .to_debug_string(),
126    ///     "[2, 3, 5, 7, 11]"
127    /// );
128    /// assert_eq!(
129    ///     Natural::primes_less_than_or_equal_to(&Natural::from(100u32))
130    ///         .collect_vec()
131    ///         .to_debug_string(),
132    ///     "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, \
133    ///     83, 89, 97]"
134    /// );
135    /// ```
136    #[inline]
137    fn primes_less_than_or_equal_to(n: &Natural) -> NaturalPrimesLessThanIterator {
138        NaturalPrimesLessThanIterator(u64::primes_less_than_or_equal_to(&u64::saturating_from(n)))
139    }
140
141    /// Returns all [`Natural`] primes.
142    ///
143    /// # Worst-case complexity (amortized)
144    /// $T(i) = O(\log \log i)$
145    ///
146    /// $M(i) = O(1)$
147    ///
148    /// where $T$ is time, $M$ is additional memory, and $i$ is the iteration index.
149    ///
150    /// # Examples
151    /// ```
152    /// use itertools::Itertools;
153    /// use malachite_base::num::conversion::traits::ConvertibleFrom;
154    /// use malachite_base::num::factorization::traits::Primes;
155    /// use malachite_base::strings::ToDebugString;
156    /// use malachite_nz::natural::Natural;
157    ///
158    /// assert_eq!(
159    ///     Natural::primes()
160    ///         .take_while(|p| u8::convertible_from(p))
161    ///         .collect_vec()
162    ///         .to_debug_string(),
163    ///     "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, \
164    ///     83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, \
165    ///     173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251]"
166    /// );
167    /// ```
168    #[inline]
169    fn primes() -> NaturalPrimesIterator {
170        NaturalPrimesIterator(u64::primes())
171    }
172}
malachite_nz/natural/factorization/primes.rs

malachite_nz/natural/factorization/
primes.rs
