All the prime numbers your heart desires in Rust!

all_primes_iter.rs

// Use this if you want [2, 3, 5.....]
use std::collections::HashMap;

/// This is a prime number generator based on [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)
/// that can be _trivially_ improved by switching to [Sieve of Atkin](https://en.wikipedia.org/wiki/Sieve_of_Atkin) for extra speed
struct PrimeIterator {
    current: u64,
    composite_to_primes: HashMap<u64, Vec<u64>>,
}

impl PrimeIterator {
    fn new() -> Self {
        PrimeIterator {
            current: 1,
            composite_to_primes: HashMap::new(),
        }
    }
}

impl Iterator for PrimeIterator {
    type Item = u64;
    
    // Algorithm based on this stackoverflow answer:
    // https://stackoverflow.com/questions/567222/simple-prime-generator-in-python
    fn next(&mut self) -> Option<Self::Item> {
        self.current += 1;

        if let Some(primes) = self.composite_to_primes.get(&self.current) {
            for prime in primes.clone() {
                self.composite_to_primes
                    .entry(self.current + prime)
                    .or_insert(Vec::new())
                    .push(prime);
            }

            self.composite_to_primes.remove(&self.current);

            self.next()
        } else {
            self.composite_to_primes
                .insert(self.current * self.current, vec![self.current]);

            Some(self.current)
        }
    }
}

fn main() {
    assert_eq!(
        PrimeIterator::new().take(100).collect::<Vec<u64>>(),
        vec![
            2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
            89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179,
            181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271,
            277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
            383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479,
            487, 491, 499, 503, 509, 521, 523, 541
        ]
    );
}

arbitrary_start_prime_iter.rs

// Use this if you want [INPUT......]

/// This is a prime number generator based on a [simple primality test described on Wikiedpa](https://en.wikipedia.org/wiki/Primality_test#Pseudocode)
/// that can be _trivially_ improved by switching is_prime implementation to [AKS_primality_test](https://en.wikipedia.org/wiki/AKS_primality_test) for extra speed
struct PrimeIterator {
    current: u64,
}

impl PrimeIterator {
    fn new() -> Self {
        PrimeIterator { current: 1 }
    }

    fn from(start: u64) -> Self {
        PrimeIterator { current: start - 1 }
    }
}

impl Iterator for PrimeIterator {
    type Item = u64;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            self.current += 1;

            if is_prime(self.current) {
                return Some(self.current);
            }
        }
    }
}

fn is_prime(potentially_prime: u64) -> bool {
    if potentially_prime <= 3 {
        return potentially_prime > 1;
    }

    if potentially_prime % 2 == 0 || potentially_prime % 3 == 0 {
        return false;
    }

    let mut i = 5;
    while i * i <= potentially_prime {
        if potentially_prime % i == 0 || potentially_prime % (i + 2) == 0 {
            return false;
        }

        i += 6;
    }

    true
}

fn main() {
    assert_eq!(
        PrimeIterator::new().take(100).collect::<Vec<u64>>(),
        vec![
            2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
            89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179,
            181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271,
            277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
            383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479,
            487, 491, 499, 503, 509, 521, 523, 541
        ]
    );

    assert_eq!(
        PrimeIterator::from(1000).take(100).collect::<Vec<u64>>(),
        vec![
            1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091,
            1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193,
            1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291,
            1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423,
            1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493,
            1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601,
            1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699,
            1709, 1721,
        ]
    );
}