devela/num/int/wrapper/impl_prime.rs
1// devela::num::int::wrapper::impl_prime
2//
3//! Implements prime-related methods for [`Int`].
4//
5// TOC
6// - signed|unsigned:
7// - is_prime
8// - prime_nth
9// - prime_pi
10// - totient
11
12use super::super::shared_docs::*;
13#[cfg(feature = "_int_isize")]
14use crate::isize_up;
15#[cfg(feature = "_int_usize")]
16use crate::usize_up;
17use crate::{iif, paste, Int, NumError::Overflow, NumResult as Result};
18
19/// Implements prime-related methods for [`Int`].
20///
21/// # Args
22/// $t: the input/output type
23/// $up: the upcasted type to do the operations on (for prime_pi)
24/// $cap: the capability feature that enables the given implementation. E.g "_int_i8".
25/// $cmp: the feature that enables the given implementation. E.g "_cmp_i8".
26///
27/// $d: the doclink suffix for the method name
28macro_rules! impl_prime {
29 () => {
30 impl_prime![signed
31 i8 |i16 :"_int_i8" :"_cmp_i8" | "",
32 i16 |i32 :"_int_i16" :"_cmp_i16" | "-1",
33 i32 |i64 :"_int_i32" :"_cmp_i32" | "-2",
34 i64 |i128 :"_int_i64" :"_cmp_i64" | "-3",
35 i128 |i128 :"_int_i128" :"_cmp_i128" | "-4",
36 isize |isize_up :"_int_isize" :"_cmp_isize" | "-5"
37 ];
38 impl_prime![unsigned
39 u8 |u16 :"_int_u8" :"_cmp_u8" | "-6",
40 u16 |u32 :"_int_u16" :"_cmp_u16" | "-7",
41 u32 |u64 :"_int_u32" :"_cmp_u32" | "-8",
42 u64 |u128 :"_int_u64" :"_cmp_u64" | "-9",
43 u128 |u128 :"_int_u128" :"_cmp_u128" | "-10",
44 usize |usize_up :"_int_usize" /*_cmp_usize*/ | "-11" // always available
45 ];
46 };
47 (signed $( $t:ty | $up:ty : $cap:literal $(: $cmp:literal)? | $d:literal ),+) => {
48 $( impl_prime![@signed $t|$up:$cap $(:$cmp)? | $d]; )+
49 };
50 (unsigned $( $t:ty | $up:ty : $cap:literal $(: $cmp:literal)? | $d:literal ),+) => {
51 $( impl_prime![@unsigned $t|$up:$cap $(:$cmp)? | $d]; )+
52 };
53 (
54 // implements signed ops
55 @signed $t:ty | $up:ty : $cap:literal $(: $cmp:literal)? | $d:literal) => { paste! {
56 #[doc = crate::doc_availability!(feature = $cap)]
57 ///
58 #[doc = "# Integer prime-related methods for `" $t "`\n\n"]
59 #[doc = "- [is_prime](#method.is_prime" $d ")"]
60 #[doc = "- [prime_nth](#method.prime_nth" $d ")"]
61 #[doc = "- [prime_pi](#method.prime_pi" $d ")"]
62 #[doc = "- [totient](#method.totient" $d ")"]
63 ///
64 #[cfg(feature = $cap )]
65 impl Int<$t> {
66 /// Returns `true` if `n` is prime.
67 ///
68 /// This approach uses optimized trial division, which means it checks
69 /// only odd numbers starting from 3 and up to the square root of the
70 /// given number. This is based on the fact that if a number is
71 /// divisible by a number larger than its square root, the result of the
72 /// division will be smaller than the square root, and it would have
73 /// already been checked in previous iterations.
74 /// # Examples
75 /// ```
76 /// # use devela::Int;
77 #[doc = "assert![Int(127_" $t ").is_prime()];"]
78 #[doc = "assert![Int(2_" $t ").is_prime()];"]
79 #[doc = "assert![!Int(1_" $t ").is_prime()];"]
80 #[doc = "assert![!Int(-2_" $t ").is_prime()];"]
81 /// ```
82 $(
83 /// # Features
84 #[doc = "This will only be *const* if the " $cmp " feature is enabled."]
85 #[cfg(feature = $cmp)]
86 )? // $cmp
87 #[must_use]
88 pub const fn is_prime(self) -> bool {
89 match self.0 {
90 ..=1 => false,
91 2..=3 => true,
92 _ => {
93 iif![self.0 % 2 == 0; return false];
94 let limit = iif![let Ok(s) = self.sqrt_floor(); s.0; unreachable!()];
95 let mut i = 3;
96 while i <= limit { iif![self.0 % i == 0; return false]; i += 2; }
97 true
98 }
99 }
100 }
101 $( // $cmp
102 #[cfg(not(feature = $cmp))] #[allow(missing_docs)]
103 pub fn is_prime(self) -> bool {
104 match self.0 {
105 ..=1 => false,
106 2..=3 => true,
107 _ => {
108 iif![self.0 % 2 == 0; return false];
109 let limit = iif![let Ok(s) = self.sqrt_floor(); s.0; unreachable!()];
110 let mut i = 3;
111 while i <= limit { iif![self.0 % i == 0; return false]; i += 2; }
112 true
113 }
114 }
115 }
116 )?
117
118 /// Finds the 0-indexed `nth` prime number.
119 ///
120 /// Note: If `nth` is negative, this function treats it as its absolute
121 /// value. For example, a value of `-3` will be treated as `3`, and the
122 /// function will return the 3rd prime number.
123 /// # Errors
124 /// Returns [`Overflow`] if the result can't fit the type.
125 /// # Examples
126 /// ```
127 /// # use devela::Int;
128 #[doc = "assert_eq![Ok(Int(2)), Int(0_" $t ").prime_nth()];"]
129 #[doc = "assert_eq![Ok(Int(3)), Int(1_" $t ").prime_nth()];"]
130 #[doc = "assert_eq![Ok(Int(127)), Int(30_" $t ").prime_nth()];"]
131 #[doc = "assert_eq![Ok(Int(127)), Int(-30_" $t ").prime_nth()];"]
132 /// # #[cfg(feature = "_int_i8")]
133 /// assert![Int(31_i8).prime_nth().is_err()];
134 /// ```
135 $(
136 /// # Features
137 #[doc = "This will only be *const* if the " $cmp " feature is enabled."]
138 #[cfg(feature = $cmp)]
139 )? // $cmp
140 pub const fn prime_nth(self) -> Result<Int<$t>> {
141 let [nth, mut count, mut i] = [self.0.abs(), 1, 2];
142 loop {
143 if Int(i).is_prime() {
144 iif![count - 1 == nth; return Ok(Int(i))];
145 count += 1;
146 }
147 i = iif![let Some(i) = i.checked_add(1); i; return Err(Overflow(None))];
148 }
149 }
150 $( // $cmp
151 #[cfg(not(feature = $cmp))] #[allow(missing_docs)]
152 pub fn prime_nth(self) -> Result<Int<$t>> {
153 let [nth, mut count, mut i] = [self.0.abs(), 1, 2];
154 loop {
155 if Int(i).is_prime() {
156 iif![count - 1 == nth; return Ok(Int(i))];
157 count += 1;
158 }
159 i = iif![let Some(i) = i.checked_add(1); i; return Err(Overflow(None))];
160 }
161 }
162 )?
163
164 /// Counts the number of primes upto and including `n`.
165 ///
166 #[doc = NOTATION_PI!()]
167 ///
168 #[doc = "It upcasts internally to [`" $up "`] for the inner operations."]
169 /// # Panics
170 /// It can panic if `n == i128|u128`, at the last iteration of a loop
171 /// that would take an unfeasable amount of time.
172 ///
173 /// # Examples
174 /// ```
175 /// # use devela::Int;
176 #[doc = "assert_eq![1, Int(2_" $t ").prime_pi()];"]
177 #[doc = "assert_eq![2, Int(3_" $t ").prime_pi()];"]
178 #[doc = "assert_eq![31, Int(127_" $t ").prime_pi()];"]
179 #[doc = "assert_eq![0, Int(-5_" $t ").prime_pi()];"]
180 /// ```
181 /// # Links
182 /// - <https://mathworld.wolfram.com/PrimeCountingFunction.html>.
183 /// - <https://en.wikipedia.org/wiki/Prime-counting_function>.
184 $(
185 /// # Features
186 #[doc = "This will only be *const* if the " $cmp " feature is enabled."]
187 #[cfg(feature = $cmp)]
188 )? // $cmp
189 pub const fn prime_pi(self) -> usize {
190 let (mut prime_count, mut i) = (0_usize, 0 as $up);
191 while i <= self.0 as $up {
192 iif![Int(i as $t).is_prime(); prime_count += 1];
193 i += 1;
194 }
195 prime_count
196 }
197 $( // $cmp
198 #[cfg(not(feature = $cmp))] #[allow(missing_docs)]
199 pub fn prime_pi(self) -> usize {
200 let (mut prime_count, mut i) = (0_usize, 0 as $up);
201 while i <= self.0 as $up {
202 iif![Int(i as $t).is_prime(); prime_count += 1];
203 i += 1;
204 }
205 prime_count
206 }
207 )?
208
209 /// Counts the number of integers $<|n|$ that are relatively prime to `n`.
210 ///
211 /// Note: If `n` is negative, this function treats it as its absolute
212 /// value. For example, a value of `-3` will be treated as `3`.
213 ///
214 /// # Formulation
215 /// ## Algorithm
216 #[doc = ALGORITHM_TOTIENT!()]
217 ///
218 /// # Examples
219 /// ```
220 /// # use devela::Int;
221 #[doc = "assert_eq![Int(2), Int(4_" $t ").totient()];"]
222 #[doc = "assert_eq![Int(6), Int(9_" $t ").totient()];"]
223 #[doc = "assert_eq![Int(12), Int(13_" $t ").totient()];"]
224 #[doc = "assert_eq![Int(22), Int(-23_" $t ").totient()];"]
225 #[doc = "assert_eq![Int(2), Int(-3_" $t ").totient()];"]
226 /// ```
227 /// # Links
228 /// - <https://en.wikipedia.org/wiki/Euler%27s_totient_function>.
229 #[must_use]
230 pub const fn totient(self) -> Int<$t> {
231 let (mut n, mut result, mut i) = (self.0.abs(), self.0.abs(), 2);
232 while i * i <= n {
233 if n % i == 0 {
234 while n % i == 0 { n /= i; }
235 result -= result / i;
236 }
237 i += 1;
238 }
239 iif![n > 1; result -= result / n];
240 Int(result)
241 }
242 }
243 }};
244 (
245 // implements unsigned ops
246 @unsigned $t:ty | $up:ty : $cap:literal $(: $cmp:literal)? | $d:literal) => { paste! {
247 #[doc = crate::doc_availability!(feature = $cap)]
248 ///
249 #[doc = "# Integer prime-related methods for `" $t "`\n\n"]
250 #[doc = "- [is_prime](#method.is_prime" $d ")"]
251 #[doc = "- [prime_nth](#method.prime_nth" $d ")"]
252 #[doc = "- [prime_pi](#method.prime_pi" $d ")"]
253 #[doc = "- [totient](#method.totient" $d ")"]
254 ///
255 #[cfg(feature = $cap )]
256 impl Int<$t> {
257 /// Returns `true` if `n` is prime.
258 ///
259 /// This approach uses optimized trial division, which means it checks
260 /// only odd numbers starting from 3 and up to the square root of the
261 /// given number. This is based on the fact that if a number is
262 /// divisible by a number larger than its square root, the result of the
263 /// division will be smaller than the square root, and it would have
264 /// already been checked in previous iterations.
265 /// # Examples
266 /// ```
267 /// # use devela::Int;
268 #[doc = "assert![Int(127_" $t ").is_prime()];"]
269 #[doc = "assert![Int(2_" $t ").is_prime()];"]
270 #[doc = "assert![!Int(1_" $t ").is_prime()];"]
271 /// ```
272 $(
273 /// # Features
274 #[doc = "This will only be *const* if the " $cmp " feature is enabled."]
275 #[cfg(feature = $cmp)]
276 )? // $cmp
277 #[must_use]
278 pub const fn is_prime(self) -> bool {
279 match self.0 {
280 ..=1 => false,
281 2..=3 => true,
282 _ => {
283 iif![self.0 % 2 == 0; return false];
284 let limit = self.sqrt_floor().0;
285 let mut i = 3;
286 while i <= limit { iif![self.0 % i == 0; return false]; i += 2; }
287 true
288 }
289 }
290 }
291 $( // $cmp
292 #[cfg(not(feature = $cmp))] #[allow(missing_docs)]
293 pub fn is_prime(self) -> bool {
294 match self.0 {
295 ..=1 => false,
296 2..=3 => true,
297 _ => {
298 iif![self.0 % 2 == 0; return false];
299 let limit = self.sqrt_floor().0;
300 let mut i = 3;
301 while i <= limit { iif![self.0 % i == 0; return false]; i += 2; }
302 true
303 }
304 }
305 }
306 )?
307
308 /// Finds the 0-indexed `nth` prime number.
309 /// # Errors
310 /// Returns [`Overflow`] if the result can't fit the type.
311 /// # Examples
312 /// ```
313 /// # use devela::Int;
314 #[doc = "assert_eq![Ok(Int(2)), Int(0_" $t ").prime_nth()];"]
315 #[doc = "assert_eq![Ok(Int(3)), Int(1_" $t ").prime_nth()];"]
316 #[doc = "assert_eq![Ok(Int(251)), Int(53_" $t ").prime_nth()];"]
317 /// // assert![Int(54_u8).prime_nth().is_err()];
318 /// ```
319 $(
320 /// # Features
321 #[doc = "This will only be *const* if the " $cmp " feature is enabled."]
322 #[cfg(feature = $cmp)]
323 )? // $cmp
324 pub const fn prime_nth(self) -> Result<Int<$t>> {
325 let [nth, mut count, mut i] = [self.0, 1, 2];
326 loop {
327 if Int(i).is_prime() {
328 iif![count - 1 == nth; return Ok(Int(i))];
329 count += 1;
330 }
331 i = iif![let Some(i) = i.checked_add(1); i; return Err(Overflow(None))];
332 }
333 }
334 $( // $cmp
335 #[cfg(not(feature = $cmp))] #[allow(missing_docs)]
336 pub fn prime_nth(self) -> Result<Int<$t>> {
337 let [nth, mut count, mut i] = [self.0, 1, 2];
338 loop {
339 if Int(i).is_prime() {
340 iif![count - 1 == nth; return Ok(Int(i))];
341 count += 1;
342 }
343 i = iif![let Some(i) = i.checked_add(1); i; return Err(Overflow(None))];
344 }
345 }
346 )?
347
348 /// Counts the number of primes upto and including `n`.
349 ///
350 #[doc = NOTATION_PI!()]
351 ///
352 #[doc = "It upcasts internally to [`" $up "`] for the inner operations."]
353 /// # Panics
354 /// It can panic if `n == i128|u128`, at the last iteration of a loop
355 /// that would take an unfeasable amount of time.
356 ///
357 /// # Examples
358 /// ```
359 /// # use devela::Int;
360 #[doc = "assert_eq![1, Int(2_" $t ").prime_pi()];"]
361 #[doc = "assert_eq![2, Int(3_" $t ").prime_pi()];"]
362 #[doc = "assert_eq![31, Int(127_" $t ").prime_pi()];"]
363 /// ```
364 /// # Links
365 /// - <https://mathworld.wolfram.com/PrimeCountingFunction.html>.
366 /// - <https://en.wikipedia.org/wiki/Prime-counting_function>.
367 $(
368 /// # Features
369 #[doc = "This will only be *const* if the " $cmp " feature is enabled."]
370 #[cfg(feature = $cmp)]
371 )? // $cmp
372 pub const fn prime_pi(self) -> usize {
373 let (mut prime_count, mut i) = (0_usize, 0 as $up);
374 while i <= self.0 as $up {
375 iif![Int(i as $t).is_prime(); prime_count += 1];
376 i += 1;
377 }
378 prime_count
379 }
380 $( // $cmp
381 #[cfg(not(feature = $cmp))] #[allow(missing_docs)]
382 pub fn prime_pi(self) -> usize {
383 let (mut prime_count, mut i) = (0_usize, 0 as $up);
384 while i <= self.0 as $up {
385 iif![Int(i as $t).is_prime(); prime_count += 1];
386 i += 1;
387 }
388 prime_count
389 }
390 )?
391
392 /// Counts the number of integers $<n$ that are relatively prime to `n`.
393 ///
394 /// # Formulation
395 /// ## Algorithm
396 #[doc = ALGORITHM_TOTIENT!()]
397 ///
398 /// # Examples
399 /// ```
400 /// # use devela::Int;
401 #[doc = "assert_eq![Int(2), Int(4_" $t ").totient()];"]
402 #[doc = "assert_eq![Int(6), Int(9_" $t ").totient()];"]
403 #[doc = "assert_eq![Int(12), Int(13_" $t ").totient()];"]
404 /// ```
405 /// # Links
406 /// - <https://en.wikipedia.org/wiki/Euler%27s_totient_function>.
407 #[must_use]
408 pub const fn totient(self) -> Int<$t> {
409 let (mut n, mut result, mut i) = (self.0, self.0, 2);
410 while i * i <= n {
411 if n % i == 0 {
412 while n % i == 0 { n /= i; }
413 result -= result / i;
414 }
415 i += 1;
416 }
417 iif![n > 1; result -= result / n];
418 Int(result)
419 }
420 }
421 }};
422}
423impl_prime!();