Sieve of Eratosthenes - lazy way

#1

Hello

I’m new to Rust. Is it possible to implement the sieve in a lazy way, like in Haskell? For example like here:

Thanks in advance

Marek

#2

Hi and welcome to Rust!

It’s not possible out of the box since Rust uses eager evaluation, but you may be able to implement it with some third party crates:

http://carllerche.github.io/eventual/eventual/struct.Stream.html

http://alexcrichton.com/futures-rs/futures/struct.Lazy.html

https://srijs.de/rust-plumbum/plumbum/

(I have to admit that I actually never used one of these crates - yet)

#3

This doesn’t address your question but it should be noted that the above is not the Sieve of Eratosthenes, despite what is commonly claimed. In particular, the above algorithm requires O(n^2 / (log n)^2) time to compute the primes less than n while the real seive requires only O(n log log n) time. See The Genuine Sieve of Eratosthenes for a more in depth explanation of the issue and a lazy implementation of the true sieve.

#4

Iterator is a Rusty way to represent a sequence of values lazily.

use std::iter::Peekable;

pub struct Primes {
    primes: Vec<u64>,
    current: u64,
}

pub fn primes() -> Primes {
    Primes {
        primes: vec![],
        current: 2,
    }
}

impl Iterator for Primes {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        for i in self.current..u64::max_value() {
            if self.primes.iter().all(|x| i % x != 0) {
                self.primes.push(i);
                self.current = i+1;
                return Some(i);
            }
        }

        panic!("Integer overflowed!")
    }
}

pub struct Factorize {
    n: u64,
    primes: Peekable<Primes>,
}

impl Iterator for Factorize {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        match (self.n, self.primes.peek().cloned()) {
            (1, _) => None,

            (m, Some(p)) => {
                if m < p * p {
                    self.n = 1;
                    return Some(m);
                }

                let (q, r) = (m / p, m % p);

                if r == 0 {
                    self.n = q;
                    Some(p)
                } else {
                    self.primes.next();
                    self.next()
                }
            }

            (_, None) => {
                unreachable!()
            }
        }
    }
}

fn factorize(n: u64) -> Factorize {
    Factorize {
        n: n,
        primes: primes().peekable(),
    }
}

fn main() {
    println!("{:?}", factorize(600851475143).max());
}

In case you need bigger values than u64, use BigUint from num crate instead.

#5

That paper is /nice/. That method of generalising the sieve of Eratosthenes to an infinite list is awesome.

#6

Thanks a lot.