Euler问题12代码优化需求：已获解但运行耗时过长

Hey there! I feel your pain—having a correct solution that drags on for 4 minutes is no fun at all, especially for Project Euler Problem 12. Let’s get this runtime down, but first, could you share your current code? Seeing exactly how you’re calculating divisors and generating triangular numbers will let me spot the specific bottlenecks holding you back.

That said, even without seeing your code, here are some tried-and-true optimizations that almost always speed up this problem drastically:

• Ditch brute-force divisor counting (the #1 slowdown for this problem): Instead of checking every number up to the triangular number to count divisors, use prime factorization. If a number (T_n = p_1^{a_1} \times p_2^{a_2} \times ... \times p_k^{a_k}), the total number of divisors is ((a_1 + 1) \times (a_2 + 1) \times ... \times (a_k + 1)). Calculating this via factorization is way faster than brute force.
• Leverage the properties of triangular numbers: Triangular numbers are (T_n = \frac{n(n+1)}{2}). Since n and n+1 are coprime (they can’t share any common factors other than 1), you can split the divisor count calculation:
  • If n is even: compute divisor count of (n/2) and divisor count of (n+1), then multiply them together.
  • If n is odd: compute divisor count of n and divisor count of ((n+1)/2), then multiply them together.
    This lets you factorize two smaller numbers instead of one big triangular number, which saves a ton of time.
• Precompute primes with a sieve: If you’re factorizing numbers repeatedly, precomputing primes up to a reasonable limit (you can estimate based on how large the target triangular number needs to be—for Problem 12, it’s not astronomically big) will make factorization much quicker.
• Optimize brute-force divisor checks (if you stick with them): If you must count divisors the naive way, only check up to the square root of the number. For every divisor d you find below sqrt(T_n), (T_n/d) is also a divisor. This cuts your work in half immediately.

Once you share your code, I can help you adapt these ideas to your specific implementation. For example, swapping a naive divisor loop with a prime-factorization-based count should bring your runtime down from minutes to seconds (or even milliseconds!).

内容的提问来源于stack exchange，提问作者05bs001