prime_data/data/prime_data.rs
1use std::{ops::RangeInclusive, cmp};
2use super::{PrimeByte, PrimeIter, CoprimeIter, error::*, utils::{IntSqrt, ContainsRange, Divisible}};
3
4/// An abstraction over storing prime numbers
5///
6/// Stores whether a number is prime or not, as a bit being one or zero. Each bit corresponds
7/// to some number that is coprime with 30. This is to avoid trivial nonprimes such as even
8/// numbers, or multiples of 3 or 5. In every integer range [30k, 30(k+1)) there are 8 of
9/// those numbers. If we take them modulo 30, we'll have a set that in this library, I call
10/// [k-values](crate::data::K_VALUES).
11///
12/// To learn more about this struct and this library as a whole, read
13/// [the guide](crate::guide).
14///
15/// # Fields
16///
17/// * Data - The bit data of wether numbers are prime or not
18/// * Range - What range of integers this data has about primes
19///
20/// They're both private fields for the sake of abstraction. The Range can be accessed through
21/// the [`PrimeData::range`] method. The data itself, as it is merely a huge collection of
22/// bits, cannot be accessed raw. However, all of the basic information you could need to
23/// reach (such as counting the amount of prime numbers, verify if a number is prime or not,
24/// or even iterate over its prime numbers) can be done through its other methods.
25///
26/// # Creating PrimeData
27///
28/// There are two basic ways of generating prime number data
29///
30/// 1. [`PrimeData::generate`]
31///
32/// The simplest one. Just give that function a range and it'll return a PrimeData instance with all
33/// primes that lie in the range you gave.
34///
35/// 2. [`PrimeData::expand`]
36///
37/// If you already have some PrimeData that has all primes until some number N, and you want to gather
38/// some new PrimeData that ranges up to N², it's more efficient to use the data you already have to
39/// "expand" into the new one you want.
40///
41/// In fact, the [generator](PrimeData::generate) method is just an abstraction over the expand function.
42/// What it does is, it calls the [`PrimeData::new`] method to generate prime numbers below 30, then
43/// expands it into bigger and bigger data until it hits `sqrt(N)`, where N is the upper bound of the
44/// data you're trying to generate. Finally, it does one last expansin from `sqrt(N)` to `N`.
45pub struct PrimeData {
46 pub(crate) data: Vec<PrimeByte>,
47 pub(crate) range: RangeInclusive<u64>,
48}
49
50impl PrimeData {
51 // methods for data generation
52
53 /// Creates a new piece of "starter data", which are all the primes below 30
54 ///
55 /// If you wish to create some starter data that gets primes below some number bigger than 30,
56 /// see [`PrimeData::generate`].
57 ///
58 /// # Examples
59 ///
60 /// ```
61 /// use prime_data::PrimeData;
62 /// let new = PrimeData::new();
63 /// let gen = PrimeData::generate(0..=30);
64 ///
65 /// assert_eq!( new.range(), gen.range());
66 /// assert_eq!(new.count_primes(), gen.count_primes());
67 /// assert_eq!( new.is_prime(29), gen.is_prime(29));
68 /// ```
69 pub fn new() -> Self {
70 Self {
71 data: vec![(0b01111111).into()],
72 range: (0..=30),
73 }
74 }
75
76 /// Generates PrimeData with all prime numbers between the given range
77 ///
78 /// # Examples
79 ///
80 /// ```
81 /// use prime_data::PrimeData;
82 /// let data = PrimeData::generate(0..=100);
83 ///
84 /// assert!( data.is_prime(2));
85 /// assert!(!data.is_prime(49));
86 ///
87 /// assert_eq!(data.range(), (0, 100));
88 /// assert_eq!(data.count_primes(), 25);
89 /// ```
90 pub fn generate(range: RangeInclusive<u64>) -> Self {
91 let (start, end) = range.into_inner();
92
93 if start > end {
94
95 }
96
97 if end <= 900 {
98 PrimeData::new().expand(start..=end)
99 } else {
100 let sqrt_end = end.sqrt_floor();
101 PrimeData::generate(0..=sqrt_end).expand(start..=end)
102 }
103 }
104
105 // methods for iteration
106
107 /// Tries to create an iterator over the given range
108 ///
109 /// Returns a [NotEnoughData](crate::error::ErrorType::NotEnoughData) error if the given range
110 /// falls out of the data (self) range.
111 ///
112 /// See [`PrimeData::iter`].
113 pub fn try_iter<'a>(&'a self, range: RangeInclusive<u64>) -> PrimeResult<PrimeIter<'a>> {
114 PrimeIter::new(self, range)
115 }
116
117 /// Creates an iterator over the given range
118 ///
119 /// Will iterate over all primes in the given range. See [`Self::try_iter`]
120 /// if you wish to return an error instead of panicking.
121 ///
122 /// If you wish to iterate over all primes within the given range, see [`PrimeData::iter_all`].
123 ///
124 /// # Panics
125 ///
126 /// Panics if the given range falls out of the data (self) range.
127 ///
128 /// # Examples
129 ///
130 /// ```
131 /// use prime_data::PrimeData;
132 /// let data = PrimeData::generate(0..=1000);
133 /// let mut iter = data.iter(472..=491);
134 ///
135 /// assert_eq!(iter.next(), Some(479));
136 /// assert_eq!(iter.next(), Some(487));
137 /// assert_eq!(iter.next(), Some(491));
138 /// assert_eq!(iter.next(), None);
139 /// ```
140 ///
141 /// ```
142 /// # use prime_data::PrimeData;
143 /// # let data = PrimeData::generate(0..=1000);
144 /// // fun fact: the biggest gap between to primes up to 1000 is 20,
145 /// // and it happens between 887 and 907
146 /// let mut iter = data.iter(888..=906);
147 ///
148 /// assert_eq!(iter.next(), None);
149 /// ```
150 pub fn iter<'a>(&'a self, range: RangeInclusive<u64>) -> PrimeIter<'a> {
151 self.try_iter(range).unwrap()
152 }
153
154 /// Iterates over all prime numbers in the given data.
155 ///
156 /// This is useful if you wish to collect all of the data's primes into a vector.
157 ///
158 /// **Warning**: PrimeData are meant to be really condensed, so when you extract raw prime vectors
159 /// from it, it could grow in size up to 8 times as itself. So collect this iterator carefully!
160 ///
161 /// If you wish to iterate over primes within a specific range, see [`PrimeData::iter`]
162 ///
163 /// # Examples
164 ///
165 /// ```
166 /// use prime_data::PrimeData;
167 /// let data = PrimeData::generate(472..=491);
168 /// let mut iter = data.iter_all();
169 ///
170 /// assert_eq!(iter.next(), Some(479));
171 /// assert_eq!(iter.next(), Some(487));
172 /// assert_eq!(iter.next(), Some(491));
173 /// assert_eq!(iter.next(), None);
174 /// ```
175 pub fn iter_all<'a>(&'a self) -> PrimeIter<'a> {
176 self.iter(self.range.clone())
177 }
178
179 // methods for expansion/generation
180
181 /// Tries to expand the current PrimeData into more PrimeData
182 ///
183 /// The expanded data will contain all primes in `range`
184 ///
185 /// Returns a [NotEnoughData](crate::error::ErrorType::NotEnoughData) error if
186 /// the given range falls out of the data (self) range.
187 ///
188 /// See [`PrimeData::expand`].
189 pub fn try_expand(&self, range: RangeInclusive<u64>) -> PrimeResult<Self> {
190
191 let (start, end) = range.bounds();
192 let end_sqrt = end.sqrt_floor();
193
194 if let Err(missing_range) = self.range.contains_range(&(7..=end_sqrt)) {
195
196 let error = PrimeError {
197 context: ErrorContext { action: ErrorAction::Modifying, source: ErrorSource::PrimeData },
198 error: ErrorType::NotEnoughData(missing_range)
199 };
200
201 return Err(error)
202 }
203
204 let mut expanded_data = Self::create_empty(range);
205 if expanded_data.is_empty() { return Ok(expanded_data) }
206
207 for prime in self.iter(7..=end_sqrt) {
208 let lower_bound = cmp::max(start.div_ceil(prime), 7);
209 let upper_bound = end.div_floor(prime);
210 for multiplier in CoprimeIter::new(lower_bound..=upper_bound) {
211 let composite_number = prime * multiplier;
212 expanded_data.set_nonprime(composite_number).unwrap();
213 }
214 }
215
216 Ok(expanded_data)
217 }
218
219 /// Expands the current PrimeData into more PrimeData
220 ///
221 /// The expanded data will contain all primes in the given range.
222 ///
223 /// See [`PrimeData::try_expand`] if you wish to return an error instead of panicking.
224 ///
225 /// # Panics
226 ///
227 /// Panics if the given PrimeData does not have enough data to expand into the given range.
228 ///
229 /// More specifically, if you wish to expand it to some prime data with range (X..=Y), the
230 /// PrimeData (self) must have a range from 7 to √Y or more.
231 ///
232 /// # Examples
233 ///
234 /// ```
235 /// use prime_data::PrimeData;
236 ///
237 /// let starter_data = PrimeData::new();
238 /// let expanded_data = starter_data.expand(59..=90);
239 ///
240 /// assert_eq!(
241 /// expanded_data.iter_all().collect::<Vec<u64>>(),
242 /// vec![59, 61, 67, 71, 73, 79, 83, 89]
243 /// );
244 /// ```
245 pub fn expand(&self, range: RangeInclusive<u64>) -> Self {
246 self.try_expand(range).unwrap()
247 }
248
249 // general methods
250
251 /// Destructures the PrimeData range into (start, end)
252 ///
253 /// **Note**: The range is inclusive.
254 ///
255 /// # Examples
256 ///
257 /// ```
258 /// use prime_data::PrimeData;
259 /// let expansion = PrimeData::generate(173..=244);
260 /// assert_eq!(expansion.range(), (173, 244));
261 /// ```
262 pub fn range(&self) -> (u64, u64) {
263 (*(self.range.start()), *(self.range.end()))
264 }
265
266 /// Retrieves the PrimeData offset
267 ///
268 /// PrimeData stores its raw data based on its range. The data starts at ⌊ range.start / 30 ⌋
269 ///
270 /// To learn more, read the [guide](crate::guide::data_structure::_2_prime_data)
271 ///
272 /// # Examples
273 ///
274 /// ```
275 /// use prime_data::PrimeData;
276 /// let data = PrimeData::new();
277 ///
278 /// assert_eq!(data.expand(29..=100).offset(), 0);
279 /// assert_eq!(data.expand(30..=100).offset(), 1);
280 /// assert_eq!(data.expand(59..=100).offset(), 1);
281 /// ```
282 pub fn offset(&self) -> usize {
283 *(self.range.start()) as usize / 30
284 }
285
286 /// Tries to verify if the given number is prime
287 ///
288 /// Returns an [OutOfBounds](crate::error::ErrorType::OutOfBounds) error if
289 /// the data range does not contain x.
290 ///
291 /// See [`PrimeData::is_prime`]
292 pub fn try_is_prime(&self, x: u64) -> PrimeResult<bool> {
293 if self.range.contains(&x) && !self.is_empty() {
294
295 if (x == 2) || (x == 3) || (x == 5) { return Ok(true) }
296 if x.divisible_by(30) { return Ok(false) }
297
298 let index = self.data_index_that_contains(x).unwrap();
299 Ok(self.data[index].is_prime((x % 30) as u8))
300 } else {
301 let error = PrimeError {
302 context: ErrorContext { action: ErrorAction::Reading, source: ErrorSource::PrimeData },
303 error: ErrorType::OutOfBounds(x)
304 };
305
306 return Err(error)
307 }
308 }
309
310 /// Verifies if the given number is prime
311 ///
312 /// **Note**: If your data starts below 7, it's heavily recommended to use the
313 /// [`check_primes`](crate::PrimeData::check_prime) method instead. This is because
314 /// this method requires the given parameter to lie within the data range. But the other only
315 /// requires that the data range includes `7..=sqrt(parameter)`.
316 ///
317 /// See [`PrimeData::try_is_prime`] if you wish to return an error instead of panicking.
318 ///
319 /// # Panics
320 ///
321 /// Panics if it falls out of the data range
322 ///
323 /// ```
324 /// use prime_data::PrimeData;
325 /// let data = PrimeData::generate(0..=900);
326 ///
327 /// assert!( data.is_prime(727));
328 /// assert!(!data.is_prime(781));
329 /// ```
330 ///
331 /// 907 is a prime number, but it's not in the range (0..=900).
332 /// ```should_panic
333 /// # use prime_data::PrimeData;
334 /// # let data = PrimeData::generate(0..=900);
335 /// assert!(data.is_prime(907));
336 /// ```
337 pub fn is_prime(&self, x: u64) -> bool {
338 self.try_is_prime(x).unwrap()
339 }
340
341 /// Tries to count the amount of prime numbers in a given range
342 ///
343 /// Returns a [NotEnoughData](crate::error::ErrorType::NotEnoughData) error if
344 /// the given range falls out of the data (self) range.
345 ///
346 /// See [`PrimeData::count_primes_in_range`].
347 pub fn try_count_primes_in_range(&self, range: RangeInclusive<u64>) -> PrimeResult<u64> {
348 if let Err(missing_range) = self.range.contains_range(&range) {
349 let error = PrimeError {
350 context: ErrorContext { action: ErrorAction::Reading, source: ErrorSource::PrimeData },
351 error: ErrorType::NotEnoughData(missing_range)
352 };
353
354 return Err(error)
355 }
356
357 if self.is_empty() { return Ok(0) }
358
359 // primedata does not take 2, 3, and 5 into account
360 let missing_primes = [2, 3, 5].iter().filter(|x| range.contains(x)).count() as u64;
361
362 let (start, end) = range.into_inner();
363
364 use cmp::Ordering;
365 match start.cmp(&end) {
366 // start > end implies range.is_empty()
367 Ordering::Greater => { Ok(0) },
368 // start = end implies range is a singular value
369 // fun fact: in maths we call this a degenerate interval
370 Ordering::Equal => { if self.is_prime(start) { Ok(1) } else { Ok(0) } },
371 // most of the time, start < end
372 Ordering::Less => {
373
374 let start_index = self.data_index_that_contains(start).unwrap();
375 let end_index = self.data_index_that_contains(end).unwrap();
376
377 let start_mod = (start % 30) as u8;
378 let end_mod = (end % 30) as u8;
379
380 if start.divisible_by(30) && end.divisible_by(30) {
381 let end_index = start_index + ((end - start) as usize / 30);
382
383 let prime_count = self.data[start_index..end_index].iter()
384 .fold(0u64, |acc, cur| acc + cur.count_primes());
385
386 Ok(missing_primes + prime_count)
387 } else if start.divisible_by(30) {
388 let prime_count = self.data[start_index..end_index].iter()
389 .fold(0u64, |acc, cur| acc + cur.count_primes());
390
391 let last_primes = self.data[end_index]
392 .count_primes_in_range(0..=end_mod);
393
394 Ok(missing_primes + prime_count + last_primes)
395 } else if end.divisible_by(30) {
396 let first_primes = self.data[start_index]
397 .count_primes_in_range(start_mod..=30);
398
399 if start_index == end_index || start + 30 > end {
400 Ok(missing_primes + first_primes)
401 } else {
402 let end_index = if end == *(self.range.end()) { end_index } else { end_index - 1 };
403
404 let prime_count = self.data[(start_index+1)..=end_index].iter()
405 .fold(0u64, |acc, cur| acc + cur.count_primes());
406
407 Ok(missing_primes + first_primes + prime_count)
408 }
409 } else {
410 // from here, we know (start % 30 != 0 != end % 30)
411 if start_index == end_index {
412 let prime_range = self.data[start_index]
413 .count_primes_in_range(start_mod..=end_mod);
414
415 Ok(missing_primes + prime_range)
416 } else {
417 let first_primes = self.data[start_index]
418 .count_primes_in_range(start_mod..=30);
419
420 let prime_count = self.data[(start_index+1)..end_index].iter()
421 .fold(0u64, |acc, cur| acc + cur.count_primes());
422
423 let last_primes = self.data[end_index]
424 .count_primes_in_range(0..=end_mod);
425
426 Ok(missing_primes + first_primes + prime_count + last_primes)
427 }
428 }
429 }
430 }
431 }
432
433 /// Counts the amount of prime numbers in a given range
434 ///
435 /// Keep in mind that if the range start is greater than the range end, Rust interprets that as an
436 /// empty range, and this function will return zero.
437 ///
438 /// See [`PrimeData::try_count_primes_in_range`] if you wish to return an error instead of panicking.
439 ///
440 /// # Examples
441 ///
442 /// ```
443 /// use prime_data::PrimeData;
444 /// let data = PrimeData::new();
445 ///
446 /// assert_eq!(data.count_primes_in_range(0..=30), 10);
447 /// assert_eq!(data.count_primes_in_range(2..=7), 4);
448 /// assert_eq!(data.count_primes_in_range(2..=2), 1);
449 /// assert_eq!(data.count_primes_in_range(24..=26), 0);
450 /// assert_eq!(data.count_primes_in_range(30..=0), 0);
451 /// ```
452 pub fn count_primes_in_range(&self, range: RangeInclusive<u64>) -> u64 {
453 self.try_count_primes_in_range(range).unwrap()
454 }
455
456 /// Counts the amount of prime numbers in the entire data
457 ///
458 /// If you wish to only count primes within a specific range, see [`PrimeData::count_primes_in_range`].
459 ///
460 /// # Examples
461 ///
462 /// ```
463 /// use prime_data::PrimeData;
464 /// let below_30 = PrimeData::new();
465 /// let below_100 = below_30.expand(0..=100);
466 /// let below_1000 = below_100.expand(0..=1000);
467 ///
468 /// assert_eq!(below_30.count_primes(), 10);
469 /// assert_eq!(below_100.count_primes(), 25);
470 /// assert_eq!(below_1000.count_primes(), 168);
471 /// ```
472 pub fn count_primes(&self) -> u64 {
473 self.count_primes_in_range(self.range.clone())
474 }
475
476 /// Verifies if the data is empty.
477 ///
478 /// Returns `true` if and only if the the range end is greater than the range start.
479 ///
480 /// # Examples
481 ///
482 /// ```
483 /// use prime_data::PrimeData;
484 ///
485 /// assert!(!PrimeData::generate(17..=71).is_empty());
486 /// assert!(!PrimeData::generate(29..=29).is_empty());
487 /// assert!( PrimeData::generate(31..=30).is_empty());
488 /// ```
489 pub fn is_empty(&self) -> bool {
490 let (start, end) = self.range();
491 start > end // || self.data.len() == 0
492 }
493
494 /// Tries to find the nth prime using the given data
495 ///
496 /// Returns a [NotEnoughData](crate::error::ErrorType::NotEnoughData) error in two situations:
497 ///
498 /// * The data starts anywhere after 7: This function requires that we count all primes up to
499 /// some bound, so we need the range to start at the beginning. Anywhere `<= 7` suffices.
500 /// * The data doesn't have n primes: Naturally, if we want the 1000th prime, we can't retrieve
501 /// it if the data only has 999.
502 ///
503 /// Returns an [OutOfBounds](crate::error::ErrorType::OutOfBounds) error if `nth` is zero.
504 ///
505 /// See [`Self::nth_prime`]
506 pub fn try_nth_prime(&self, nth: u64) -> PrimeResult<u64> {
507
508 match nth {
509 0 => {
510 let error = PrimeError {
511 context: ErrorContext { action: ErrorAction::Reading, source: ErrorSource::PrimeData },
512 error: ErrorType::OutOfBounds(nth)
513 };
514
515 return Err(error)
516 },
517 1 => return Ok(2),
518 2 => return Ok(3),
519 3 => return Ok(5),
520 _ => {}
521 }
522
523 let total_primes = self.count_primes();
524
525 if let Err(missing_range) = self.range.contains_range(&(7..=total_primes)) {
526
527 let error = PrimeError {
528 context: ErrorContext { action: ErrorAction::Reading, source: ErrorSource::PrimeData },
529 error: ErrorType::NotEnoughData(missing_range)
530 };
531
532 return Err(error)
533 }
534
535 let (unchecked_start, unchecked_end) = super::estimate::nth_prime_bounds(nth).into_inner();
536 let start = std::cmp::max(7, unchecked_start);
537 let end = std::cmp::min(*(self.range.end()), unchecked_end);
538
539 let offset = 3 + self.count_primes_in_range(7..=start) - (if self.is_prime(start) { 1 } else { 0 });
540
541 Ok(self.iter(start..=end).nth((nth - offset - 1) as usize).unwrap())
542 }
543
544 /// Retrieves the nth prime number from some data
545 ///
546 /// If we call "nth prime number" as p(n), we have that p(1) = 2, because 2 is the first prime
547 /// number. p(2) = 3, and so on. Therefore, the "zeroth" prime number is not defined.
548 ///
549 /// See [`Self::try_nth_prime`] if you wish to return an error instead of panicking.
550 ///
551 /// # Panics
552 ///
553 /// Panics in the following situations:
554 ///
555 /// * `nth` is zero
556 /// * PrimeData (self) starts after 7
557 /// * PrimeData (self) ends before `nth`
558 ///
559 /// # Examples
560 ///
561 /// ```
562 /// use prime_data::PrimeData;
563 /// let data = PrimeData::generate(7..=105_000);
564 ///
565 /// assert_eq!(data.nth_prime(1), 2);
566 /// assert_eq!(data.nth_prime(4), 7);
567 /// assert_eq!(data.nth_prime(19), 67);
568 /// assert_eq!(data.nth_prime(10001), 104743);
569 /// ```
570 pub fn nth_prime(&self, nth: u64) -> u64 {
571 self.try_nth_prime(nth).unwrap()
572 }
573
574 /// Tries to verify if the given number is prime
575 ///
576 /// Returns a [NotEnoughData](crate::error::ErrorType::NotEnoughData) error if both are true:
577 ///
578 /// * The data range does not include x
579 /// * The data range does not contain the range between 7 and √x
580 ///
581 /// See [`Self::check_prime`]
582 pub fn try_check_prime(&self, x: u64) -> PrimeResult<bool> {
583 if self.range.contains(&x) {
584 self.try_is_prime(x)
585 } else {
586
587 let sqrt = x.sqrt_floor();
588
589 if let Err(missing_range) = self.range.contains_range(&(7..=sqrt)) {
590
591 let error = PrimeError {
592 context: ErrorContext { action: ErrorAction::Reading, source: ErrorSource::PrimeData },
593 error: ErrorType::NotEnoughData(missing_range)
594 };
595
596 return Err(error)
597 }
598
599 if (x == 2) || (x == 3) || (x == 5) { return Ok(true) }
600 if x.divisible_by(30) { return Ok(false) }
601
602 for prime in self.iter(7..=sqrt) {
603 if x.divisible_by(prime) { return Ok(false) }
604 }
605
606 Ok(true)
607 }
608 }
609
610 /// Verifies if the given number is prime
611 ///
612 /// If we have information of all prime numbers between 0 and √x, we can verify if x is prime
613 /// by checking if none of those primes divide x. Therefore, when calling this function, if x
614 /// lies inside the data, it's O(1), but if the data has information about all primes up to √x,
615 /// it's O(n).
616 ///
617 /// See [`Self::try_check_prime`] if you wish to return an error instead of panicking.
618 ///
619 /// # Panics
620 ///
621 /// Panics if both are true:
622 ///
623 /// * The data range does not include x
624 /// * The data range does not contain the range between 7 and √x
625 ///
626 /// # Examples
627 ///
628 /// ```
629 /// use prime_data::PrimeData;
630 ///
631 /// let data = PrimeData::generate(7..=35);
632 ///
633 /// assert!( data.check_prime(7)); // O(1)
634 /// assert!(!data.check_prime(35)); // O(1)
635 /// assert!( data.check_prime(1123)); // O(n)
636 /// assert!(!data.check_prime(1225)); // O(n)
637 /// ```
638 pub fn check_prime(&self, x: u64) -> bool {
639 self.try_check_prime(x).unwrap()
640 }
641
642 /// Tries to factorize the given number into prime factors.
643 ///
644 /// Returns a [NotEnoughData](crate::error::ErrorType::NotEnoughData) error if
645 /// the data (self) range does not contain the range `2..=sqrt(x)`.
646 ///
647 /// See [`Self::factorize`]
648 #[cfg(feature = "factors")]
649 pub fn try_factorize(&self, x: u64) -> PrimeResult<super::Factorization> {
650
651 let mut number = x;
652 let sqrt = x.sqrt_floor();
653
654 if let Err(missing_range) = self.range.contains_range(&(2..=sqrt)) {
655 let error = PrimeError {
656 context: ErrorContext { action: ErrorAction::Reading, source: ErrorSource::PrimeData },
657 error: ErrorType::NotEnoughData(missing_range)
658 };
659
660 return Err(error)
661 }
662
663 let mut factorization = super::Factorization::new();
664
665 for prime in self.iter(2..=sqrt) {
666 while number % prime == 0 {
667 let other_factor = number / prime;
668 factorization.add_factor(prime);
669 number /= prime;
670 }
671 }
672
673 if number > 1 {
674 factorization.add_factor(number);
675 }
676
677 Ok(factorization)
678 }
679
680 /// Factorizes the given number into prime factors.
681 ///
682 /// See [`Self::try_factorize`] if you wish to return an error instead of panicking.
683 ///
684 /// # Panics
685 ///
686 /// Panics if the data (self) range does not contain the range `2..=sqrt(x)`.
687 ///
688 /// # Examples
689 ///
690 /// This function returns a [Factorization](super::Factorization) struct. Read
691 /// to the struct's documentation for its methods and examples.
692 #[cfg(feature = "factors")]
693 pub fn factorize(&self, x: u64) -> super::Factorization {
694 self.try_factorize(x).unwrap()
695 }
696}
697
698// private methods
699impl PrimeData {
700 // Creates "empty" data, with all bits set to one.
701 // Should only be called by expansion functions.
702 fn create_empty(range: RangeInclusive<u64>) -> Self {
703 let data_start = (*range.start()).div_floor(30);
704 let data_end = (*range.end()).div_ceil(30);
705
706 if data_start >= data_end {
707 return Self { data: vec![], range }
708 }
709
710 let data_length = (data_end - data_start) as usize;
711 let mut data = vec![PrimeByte::new(); data_length];
712
713 // We want 1 to be set as nonprime by default
714 if data_start == 0 {
715 data[0].set_nonprime(1).unwrap();
716 }
717
718 Self { data, range }
719 }
720
721 fn set_nonprime(&mut self, nonprime: u64) -> PrimeResult<bool> {
722 if self.range.contains(&nonprime) {
723 let data_index = (nonprime / 30) as usize - self.offset();
724 let k_value = (nonprime % 30) as u8;
725
726 match self.data[data_index].set_nonprime(k_value) {
727 Ok(boolean) => Ok(boolean),
728 Err(()) => {
729 let error = PrimeError {
730 context: ErrorContext {
731 action: ErrorAction::Modifying,
732 source: ErrorSource::PrimeData
733 },
734 error: ErrorType::OutOfBounds(nonprime)
735 };
736
737 Err(error)
738 },
739 }
740 } else {
741
742 let error = PrimeError {
743 context: ErrorContext { action: ErrorAction::Modifying, source: ErrorSource::PrimeData },
744 error: ErrorType::OutOfBounds(nonprime)
745 };
746
747 Err(error)
748 }
749 }
750
751 // Retrieves an index such that `self.data[index]` contains x
752 // Returns none if x is out of `self.range`]
753 //
754 // if x % 30 == 0, it'll give you the range [x, x+30], unless
755 // x is equal to the range ending. this means the data does not
756 // contain [x, x+30] and will instead return [x-30, x]
757 fn data_index_that_contains(&self, x: u64) -> Option<usize> {
758
759 if self.is_empty() { return None }
760
761 if self.range.contains(&x) {
762 let result = (x / 30) as usize - self.offset();
763
764 if result >= self.data.len() {
765 if x.divisible_by(30) {
766 Some(result - 1)
767 } else {
768 panic!("Unexpected error! This should be removed once unit tested!")
769 }
770 } else {
771 Some(result)
772 }
773 } else {
774 None
775 }
776 }
777}
778
779use std::fmt;
780impl fmt::Debug for PrimeData {
781 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
782 let digit_len = digit_len(self.range().1);
783 let byte_full_size = digit_len + 10;
784 let bytes_per_line = bytes_per_line(byte_full_size);
785 let line_len = bytes_per_line * (byte_full_size + 1) + 3;
786
787 let title_and_range = format!("{}\n{}\n", title(line_len), range(line_len, self.range()));
788
789 let mut data_str = String::new();
790 let offset = self.offset();
791 for (idx, chunk) in self.data.chunks(bytes_per_line).enumerate() {
792 let outer_offset = offset + (idx * bytes_per_line);
793 let mut starter = format!("# ");
794 for (i, byte) in chunk.iter().enumerate() {
795 let inner_offset = outer_offset + i;
796 starter.push_str(&format!("{} ", print_byte(byte, inner_offset, digit_len)));
797 }
798 starter.push_str(&format!("{}#", " ".repeat(line_len - starter.len() - 1)));
799
800 data_str.push_str(&format!("{}\n", starter));
801 }
802
803 let bottom = "#".repeat(line_len);
804 let full_debug_string = format!("{}{}{}", title_and_range, data_str, bottom);
805 write!(f, "\n{}", full_debug_string)
806 }
807}
808
809// debug stuff
810 fn digit_len(max: u64) -> usize {
811 format!("{}", max).len()
812 }
813
814 fn print_byte(byte: &PrimeByte, offset: usize, digit_len: usize) -> String {
815 format!("{:>width$}{}", offset * 30, byte, width = digit_len)
816 }
817
818 fn bytes_per_line(byte_full_size: usize) -> usize {
819 128 / byte_full_size
820 }
821
822 fn title(line_len: usize) -> String {
823 let title = "### PRIME DATA ";
824 let filler = "#".repeat(line_len - title.len());
825 format!("{}{}", title, filler)
826 }
827
828 fn range(line_len: usize, range: (u64, u64)) -> String {
829 let (start, end) = range;
830 let left = format!("Range: ({} -> {})", start, end);
831 let right = " ".repeat(line_len - left.len() - 4);
832 format!("# {}{} #", left, right)
833 }
834
835#[cfg(test)]
836mod tests {}