rust - 糟糕的 Rust 代码优化还是我做得还不够？ (欧拉#757)

Question

我正在尝试解决我的第一个项目 Euler 问题，只是为了玩 Rust，但被困在似乎需要极长计算时间的问题上
问题:
https://projecteuler.net/problem=757
我想出了这段代码来尝试解决它，我能够在 ~245 毫秒内解决基本问题(最多 10^6)并获得 2,851 的预期结果。

use std::time::Instant;

fn factor(num: u64) -> Vec<u64> {
    let mut counter = 1;
    let mut factors = Vec::with_capacity(((num as f64).log(10.0)*100.0) as _);
    while counter <= (num as f64).sqrt() as _ {
        let div = num / counter;
        let rem = num % counter;
        if rem == 0 {
            factors.push(counter);
            factors.push(div);
        }
        counter += 1
    }
    factors.shrink_to_fit();
    factors
}

fn main() {
    let now = Instant::now();
    let max = 10u64.pow(6);
    let mut counter = 0;
    'a: for i in 1..max {
        // Optimization: All numbers in the pattern appear to be evenly divisible by 4
        let div4 = i / 4;
        let mod4 = i % 4;
        if mod4 != 0 {continue}
        // Optimization: And the remainder of that divided by 3 is always 0 or 1
        if div4 % 3 > 1 {continue}
        let mut factors = factor(i);
        if factors.len() >= 4 {
            // Optimization: The later found factors seem to be the most likely to fit the pattern, so try them first
            factors.reverse();
            let pairs: Vec<_> = factors.chunks(2).collect();
            for paira in pairs.iter() {
                for pairb in pairs.iter() {
                    if pairb[0] + pairb[1] == paira[0] + paira[1] + 1 {
                        counter += 1;
                        continue 'a;
                    }
                }
            }
        }
    }
    println!("{}, {} ms", counter, now.elapsed().as_millis());
}

看起来我的代码在因式分解上花费了最多的时间，并且在我寻找比我自己能够想出的更有效的因式分解算法时，我找不到任何已经制作的 Rust 代码(我确实找到的代码实际上更慢。)但我做了一个模拟来估计即使我有一个完美的因式分解算法也需要多长时间，并且需要 13 天才能找到所有不超过 10^14 的数字，并且没有因式分解此代码的一部分。可能不是这个问题的创造者的意图。
鉴于我对编程比较陌生，是否有一些我不知道的概念或编程方法(比如使用哈希图进行快速查找)可以在这种情况下使用？或者解决方案是否涉及发现数字中的模式并进行像我迄今为止发现的优化那样的优化？

Answer 1

如 Vec::push当向量达到其容量时调用，它将重新分配其内部缓冲区以将大小加倍并将其所有元素复制到此新分配中。Vec::new()创建一个没有分配空间的向量，因此它将进行重新分配。
您可以使用 Vec::with_capacity((num/2) as usize)为避免这种情况，只需分配您可能需要的最大值。