Sieve of Eratosthenes: Difference between revisions
Content deleted Content added
→Tree-merging incremental sieve: promote improved wheels to sub-section. NB the language highlighting with primed names is pretty bad! |
→{{header|Rust}}: added new Rust solution. |
||
Line 11,396:
=={{header|Rust}}==
[[Category:Rust]]
===Unboxed Iterator===
A slightly more idiomatic, optimized and modern iterator output example.
<lang rust>fn primes(n: usize) -> impl Iterator<Item = usize> {
const START: usize = 2;
if n < START {
Vec::new()
} else {
let mut is_prime = vec![true; n + 1 - START];
let limit = (n as f64).sqrt() as usize;
for i in START..limit + 1 {
let mut it = is_prime[i - START..].iter_mut().step_by(i);
if let Some(true) = it.next() {
it.for_each(|x| *x = false);
}
}
is_prime
}
.into_iter()
.enumerate()
.filter_map(|(e, b)| if b { Some(e + START) } else { None })
}</lang>
Notes:
# Starting at an offset of 2 means that an <code>n < 2</code> input requires zero allocations, because <code>Vec::new()</code> doesn't allocate memory until elements are pushed into it.
# Using <code>Vec</code> as an output to the <code>if .. {} else {}</code> condition means the output is statically deterministic, avoiding the need for a boxed trait object.
# Iterating <code>is_prime</code> with <code>.iter_mut()</code> and then using <code>.step_by(i)</code> makes all the optimizations required, and removes a lot of tediousness.
# Returning <code>impl Iterator</code> allows for static dispatching instead of dynamic dispatching, which is possible because the type is now statically known at compile time, making the zero input/output condition an order of magnitude faster.
===Sieve of Eratosthenes - No optimization===
<lang rust>fn simple_sieve(limit: usize) -> Vec<usize> {
| |||