1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130
/// Provides an iterator for generating prime numbers.
///
/// ```
/// # use zetik_prime::Prime;
/// let mut primes = Prime::default();
/// assert_eq!(primes.next(), Some(2));
/// assert_eq!(primes.next(), Some(3));
/// assert_eq!(primes.next(), Some(5));
/// assert_eq!(primes.next(), Some(7));
/// ```
#[derive(Default, PartialEq, Eq)]
pub struct Prime {
primes: Vec<u64>,
}
impl Prime {
/// Equivilent to `Prime::default()`
///
/// ```
/// # use zetik_prime::Prime;
/// let mut new = Prime::new();
/// let mut default = Prime::default();
/// assert_eq!(new, default);
/// ```
pub fn new() -> Prime {
Default::default()
}
/// Returns the prime number after the given argument.
///
/// Return value is an option to keep inline with `<Iterator>.next()`
///
/// ```
/// # use zetik_prime::Prime;
/// let mut primes = Prime::default();
/// assert_eq!(primes.next_after(1000), Some(1009));
/// ```
pub fn next_after(&mut self, num: u64) -> Option<u64> {
Some(loop {
let next = self.next().unwrap();
if next > num {
break next;
}
})
}
pub fn is_empty(&self) -> bool {
self.primes.is_empty()
}
/// Returns the length of the inner `Vec<u64>`
///
/// ```
/// # use zetik_prime::Prime;
/// let mut primes = Prime::default();
/// primes.nth(100);
/// assert_eq!(primes.len(), 101);
/// ```
pub fn len(&self) -> usize {
self.primes.len()
}
}
/// Returns the prime factors of the given argument.
///
/// ```
/// # use zetik_prime::prime_factors;
/// assert_eq!(prime_factors(126), [2, 3, 3, 7]);
/// assert_eq!(prime_factors(12345), [3, 5, 823]);
/// assert_eq!(prime_factors(2 * 3 * 5 * 7 * 11), [2, 3, 5, 7, 11]);
/// ```
pub fn prime_factors(num: u64) -> Vec<u64> {
let mut facts = vec![];
let mut num = num;
for i in 2.. {
while num % i == 0 {
num /= i;
facts.push(i);
}
if num == 1 {
break;
}
}
facts
}
impl Iterator for Prime {
type Item = u64;
fn next(&mut self) -> Option<Self::Item> {
let new = if let Some(&last) = self.primes.last() {
let mut a = if last < 3 { 3 } else { last + 2 };
for cnt in (a..).step_by(2) {
let mut is_prime = true;
let cnt_sqr = f32::sqrt(cnt as f32) as u64;
for &p in &self.primes {
if cnt % p == 0 {
is_prime = false;
break;
}
if p > cnt_sqr {
break;
}
}
if is_prime {
a = cnt;
break;
}
}
a
} else {
2
};
self.primes.push(new);
Some(new)
}
}
impl core::fmt::Debug for Prime {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{:?}", self.primes)
}
}