如何使用 Eratosthenes Sieve 设置第 n 个素数的数组大小上限？

Question

以 n 作为输入，我试图输出第 n 个素数。 Eratosthenes Sieve 似乎是一个很好的方法，但我在筛选数组的大小方面遇到了问题。

我使用一个数组，其中每个成员都是 1，代表一个数字。如果筛子过滤掉了数字，则该值变为 0，这意味着该数字不是素数。一旦到达值为 1 的第 n 个成员，索引值为 returned.

我正在尝试为任何给定的 n 设置合理的数组大小。但是我有两个问题。

因为我似乎需要将数组的大小设置为一个常数值，所以我找不到一种方法可以使用n的大小来近似所需的数组大小。这意味着我总是使用 10e6 大小的数组，即使 n 很小。
此方法依赖于大型数组，因为它使用早期值来更改后期值。这意味着对于 n > 10e7，我的数组会破坏堆栈。有没有办法不用堆就可以解决这个问题？

我试过使用 const 来解决第一个问题：

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];
    ...
}

但是，它无法绕过具有固定数组大小的要求。

有什么建议吗？另外，我对生锈很陌生，欢迎任何让它更像生锈的建议。

下面是我的尝试，它有一个固定大小的数组并且适用于 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
}

编辑：感谢您的精彩回答！我已将函数更改为使用 (n * (n * n.ln()).ln()) 估计，将 usize 数组替换为布尔向量。遗憾的是，我似乎无法使这个较低的值仅在堆栈上起作用，因为当数组大小接近近似值时，基于数组的方法比基于向量的方法更快。

我尝试使用早期的 return 并放弃 output 但不知道如何让它工作。我在这个编辑的末尾有我的代码，其中注释掉了我试图放置早期 return 和 unreachable!() 的行，但它总是让我感到恐慌。如果有人能指出我的错误那就太好了。

我打算按照 NieDzejkob 的建议将最里面的 while 循环更改为 for 循环，但是当我运行速度数字 while 与 for 相比，我发现 while 循环更快。有谁知道为什么会这样？

此外，我在 0-9、11 和 12 素数方面遇到了一些问题，所以我只是将近似值设置为在这个运行ge 以上工作。

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
    }
}

Answer 1

使用可变数组大小

不幸的是，堆栈上不可能有可变长度数组。您可以使用向量在堆上分配它：

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

正在估算所需尺寸

这个问题has been described here before，虽然不是在 Rust 中。这个想法是对第n个素数使用上限公式：

p_n < n ln (n ln n)

对于u32，你可以用浮点数来计算：

// 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 代码风格

就改进您的代码而言，我不明白您为什么要使用 usizes，因为您只存储了 0 和 1。这是 bool 的完美用例，应该会导致内存使用量减少八倍。

output 变量并不是必须的，最好使用 return 提前退出。然后，您可以用 unreachable!().

标记函数的结尾

另外，最里面的循环也可以这样写，我觉得这样更好：

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

Answer 2

当 n ≥ 6 时，筛子尺寸的标准公式是 ln (n ln n)。参见 Wikipedia。

如果您使用上限函数 ceiling(ln (n ln(n))，则该公式适用于 n >= 3。但是，它不适用于 1 和 2。对于 n=1，您在第二次调用 ln() 时出现 ln(0) 错误，但它应该是 2。对于 n=2，筛子需要是 3。

因此，检查 n <3，如下所示。

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
    }
}

如何使用 Eratosthenes Sieve 设置第 n 个素数的数组大小上限？

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

arrays

sieve-of-eratosthenes

rust

使用可变数组大小

正在估算所需尺寸

Rust 代码风格