Genuine Lazy Sieve of Eratosthenese https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

lazy_sieve.rs

use std::cmp::Ordering;
use std::collections::BinaryHeap;

// I can't come up with a better name for this :P
#[derive(Debug, PartialEq, Eq)]
struct Pair {
    prime: u128,
    multiple: u128,
}

// We only need to compare the multiple as that is the priority we key on
impl Ord for Pair {
    fn cmp(&self, other: &Self) -> Ordering {
        other.multiple.cmp(&self.multiple) // Reverse so we get a min heap
    }
}

impl PartialOrd for Pair {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

struct PrimeIterator {
    num: u128,
    heap: BinaryHeap<Pair>,
}

impl PrimeIterator {
    fn new() -> Self {
        PrimeIterator {
            num: 2,
            heap: BinaryHeap::new(),
        }
    }
}

impl Iterator for PrimeIterator {
    type Item = u128;

    // This is an infinite iterator, so it should never return None
    fn next(&mut self) -> Option<Self::Item> {
        while let Some(&Pair { multiple, .. }) = self.heap.peek() {
            if self.num == multiple {
                loop {
                    match self.heap.peek() {
                        Some(&Pair { prime, multiple }) if self.num == multiple => {
                            self.heap.pop();
                            self.heap.push(Pair {
                                prime,
                                multiple: multiple + prime,
                            });
                        }
                        Some(_) => break,
                        None => unreachable!(),
                    }
                }
                self.num += 1;
            } else {
                break;
            }
        }

        // self.num is now a new prime
        self.heap.push(Pair {
            prime: self.num,
            multiple: self.num * self.num,
        });
        self.num += 1;

        Some(self.num - 1)
    }
}

fn main() {
    let sieve = PrimeIterator::new();

    assert!(sieve.take(100).all(|p| (2..p).all(|d| p % d != 0)));
}