recursion - 有没有办法优化这段代码，使其不会溢出堆栈？

Question

我正在研究第三个欧拉计划问题:

fn main() {
    println!("{}", p3());
}

fn p3() -> u64 {
    let divs = divisors(1, 600851475143, vec![]);
    let mut max = 0;
    for x in divs {
        if prime(x, 0, false) && x > max {
            max = x
        }
    }
    max
}

fn divisors(i: u64, n: u64, div: Vec<u64>) -> Vec<u64> {
    let mut temp = div;
    if i * i > n {
        temp
    } else {
        if n % i == 0 {
            temp.push(i);
            temp.push(n / i);
        }
        divisors(i + 2, n, temp)
    }
}

fn prime(n: u64, i: u64, skip: bool) -> bool {
    if !skip {
        if n == 2 || n == 3 {
            true
        } else if n % 3 == 0 || n % 2 == 0 {
            false
        } else {
            prime(n, 5, true)
        }
    } else {
        if i * i > n {
            true
        } else if n % i == 0 || n % (i + 2) == 0 {
            false
        } else {
            prime(n, i + 6, true)
        }
    }
}

值 600851475143 是在某个时刻导致它溢出的值。如果我将其替换为 10¹⁰ 数量级或更小的任何值，它会返回一个答案。在将其保留为递归解决方案的同时，有没有办法:

1. 增加筹码量？
2. 优化我的代码，使其不返回fatal runtime: stack overflow 错误？

我知道这可以迭代完成，但我不想那样做。

Answer 1

包含 600 * 10⁹ u64 的向量意味着您将需要 4.8 TB 的 RAM 或交换空间。

我敢肯定，对于这个问题，您不需要它，您在这里缺少一些数学知识:扫描到 600851475143 的平方根就足够了。您也可以使用 Sieve of Eratosthenes 来加速程序。 .

Project Euler 可以很好地提高您的数学技能，但它不能特别帮助您学习任何编程语言。为了学习 Rust，我从 Exercism 开始.