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)
    }
}