Hello

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

https://github.com/zacharydenton/euler/blob/master/003/prime-factor.hs

Thanks in advance

Marek

Hello

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

https://github.com/zacharydenton/euler/blob/master/003/prime-factor.hs

Thanks in advance

Marek

1 Like

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:

https://github.com/reem/rust-lazy

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)

1 Like

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.

1 Like

`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.

2 Likes

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

Thanks a lot.