How to set upper bound in array size in nth prime using Eratoshenes Sieve?

user_12197651 0
Viewed 271

With n as input, I am trying to output the nth prime. The Eratosthenes Sieve seemed a good way to do this, but I am having trouble with the size of the array to be sieved.

I use an array in which every member is 1, and represents a number. If the sieve filters out the number, the value is changed to 0, which means the number is not prime. Once it arrives at the nth member which has a value of 1, the index value is returned.

I am trying to set a reasonable array size for any given n. But I have two problems.

  1. Because I seem to be required to set the size of the array to a constant value, I cannot find a way to use the size of n to approximate the required array size. This means I am always using an array of 10e6 magnitude, even when n is small.

  2. This approach relies on having a large array, because it uses early values to change later values. This means that for n > 10e7, my array blows the stack. Is there a way around this problem without going to the heap?

I've tried to solve the first problem by using const like this:

pub fn nth(n: u32) -> u32 {
    const ARRAY_SIZE : usize = f(n) // where f(n) is some approximation of required array size
    let mut primes: [usize; ARRAY_SIZE] = [1; ARRAY_SIZE];
    ...
}

However, it does not get around the requirement to have a fixed array size.

Any suggestions? Also I am very new to rust and any suggestions to make it more rust-like are welcome.

Below is my attempt which has a fixed size array and works for values of n <= 10,000:

pub fn nth(n: u32) -> u32 {
    // Eratosthene's Sieve Algorithm
    let mut output: u32 = 0;
    let mut primes: [usize; 104_827] = [1; 104_827];
    primes[0] = 0;
    primes[1] = 0;

    let mut prime_count = 0;

    for i in 2..(primes.len() as usize) {
        if primes[i] == 1 {
            if prime_count == n as usize { output = i as u32; }
            prime_count += 1;

            let mut j: usize = 2;
            while i * j <= primes.len() as usize {
                primes[i * j] = 0;
                j += 1;
            }
        }
    }
    output
}

edit: Thanks for the great answers! I've changed the function to use the (n * (n * n.ln()).ln()) estimation, replaced the array of usize with a vector of bools. Shame I can't seem to make the lower values of this work on just the stack, because the array-based method is faster than the vector-based method, when the array size is close to the approximation.

I tried to use the early return and dispense with output but couldn't figure out how to make it work. I have my code at the end of this edit with lines commented out with where I tried to put the early return and unreachable!() but it always panicked on me. If someone can point out my mistake that would be great.

I was going to change the inner-most while loop into a for loop as suggested by NieDzejkob, but when I ran the numbers for speed of while vs for, I found the while loop to be faster. Does anyone know why this might be?

Also I had some problems with 0-9th, 11th, and 12th primes, so I just set the approximation to work above this range.

100th prime while_func = 547, for_func = 547
prime while_func 152.431µs vs for_func 216.043µs
1000th prime while_func = 7927, for_func = 7927
prime while_func 2.099213ms vs for_func 3.362854ms
10000th prime while_func = 104743, for_func = 104743
prime while_func 28.162967ms vs for_func 44.967197ms
100000th prime while_func = 1299721, for_func = 1299721
prime while_func 339.324756ms vs for_func 559.755934ms
1000000th prime while_func = 15485867, for_func = 15485867
prime while_func 4.151047728s vs for_func 6.950281943s 

pub fn nth(n: u32) -> u32 {
    // Eratosthene's Sieve Algorithm
    let estimate = estimate_size(n);
    let mut primes: Vec<bool> = vec![true; estimate + 1];

    primes[0] = false;
    primes[1] = false;

    let mut output: u32 = 0; // remove if unreachable!() works
    let mut prime_count: u32 = 0;

    for i in 2..(estimate) {
        if primes[i] == true {
            if prime_count == n { output = i as u32; }
//            if prime_count == n { return i as u32; }
            prime_count += 1;

            let mut j: usize = 2;
            while i * j <= estimate {
                primes[i * j] = false;
                j += 1;
            }
//            for j in (2*i ..= estimate).step_by(i) {
//                primes[j] = false;
//            }
        }
    }
    output
//  unreachable!()
}

fn estimate_size(n: u32) -> usize {
    if n < 14 {
        44 as usize
    } else {
        let n = n as f64;
        (n * (n * n.ln()).ln()).ceil() as usize
    }
}
rust sieve-of-eratosthenes arrays
2 Answers

Using a variable array size

Unfortunately, it is not possible to have a variable-length array on the stack. You can use a vector to allocate it on the heap:

let mut primes: Vec<bool> = vec![true; estimate_size(n)];

Estimating the required size

This problem has been described here before, although not in Rust. The idea is to use an upper bound formula for the n-th prime:

pn < n ln (n ln n)

For u32, you can use floats to calculate this:

// I'm making it a separate function for demonstration purposes. You might want to not do that.
fn estimate_size(n: u32) -> usize {
    let n = n as f64;
    (n * (n * n.ln()).ln()).ceil() as usize
}

Rust code style

As far as improving your code goes, I don't see why you're using usizes, since you're only storing zeroes and ones. This is a perfect use-case for bool, which should result in an eight-fold reduction in memory use.

The output variable isn't really necessary, it would be better to use a return to exit early. You could then label the end of the function with unreachable!().

Also, the innermost loop can also be written this way, and I think that's nicer:

for j in (2*i ..= primes.len()).step_by(i) {
    primes[j] = false;
}
user_58639870

The standard formula for the size of a sieve is ln (n ln n) for n ≥ 6. See Wikipedia.

If you use the ceiling function, ceiling(ln (n ln(n)), then the formula works for n >= 3. However, it does not work for 1 and 2. For n=1, you get an error for taking ln(0) on the second ln() call, but it should be 2. For n=2, the sieve needs to be 3.

So, check for n <3 as shown below. 

fn get_sieve_size(n: u32) -> usize {
    if n < 3 {
        (n + 1) as usize
    } else {
        let n = n as f64;
        (n * (n * n.ln()).ln()).ceil() as usize
    }
}
user_49833980
Related