Home > Software engineering >  Sieve of Eratosthenes in rust
Sieve of Eratosthenes in rust

Time:10-10

I am trying to code a sieve of Eratosthenes in rust. (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), As I want to use the code multiple times I am creating a function to perform the sieve, however I have run into an issue. Ideally I would like to use an array rather than a vector for performance reasons as (provided the input value is hardcoded) the size of the sieve is known at compile time.

Is there some way of achieving something similar to:

/// get all primes up to max using a sieve of eratosthenes
fn eratosthenes_primes(&max: i32) {
// where &max is known at compile time
    let is_prime = [i32; max   1];
    // logic
}

Thanks

CodePudding user response:

The problem here is that max, being a parameter, is not known at compile time. What you probably want is called const generics.

Sadly, they are not fully stabilized yet. Specifically, const generic expressions are not stabilized at the time of writing.

So you can pass in the value and you can create an array from it, but you cannot do math with it yet (meaning the max 1 is not yet possible).

So what you can currently do is:

fn eratosthenes_primes<const MAX: usize>() -> [bool; MAX] {
    let is_prime = [true; MAX];

    // ... logic to compute primes ...

    is_prime
}

When using it, you often don't even have to explicitly state the number, Rust can infer it from the output type:

let primes: [bool; 100] = eratosthenes_primes();

If course you can also specify it excplicitly:

let primes = eratosthenes_primes::<100>();
  • Related