Python循环优化求助：加速Project Euler #351亿级计算代码

Let's break down why your current code can't handle 100 million in reasonable time, then fix it with mathematical insights and efficient algorithms:

1. Inefficient Coprimality Check #

Your code uses Fraction(y/x).limit_denominator() to check if a fraction can be reduced—this is an extremely roundabout, slow way to determine if y and x are coprime. This method involves unnecessary fraction parsing and string operations, when all you need is to calculate the greatest common divisor (gcd) of y and x: if gcd(y, x) == 1, the fraction is in simplest terms; otherwise, it can be reduced.

2. Crippling O(n²) Time Complexity #

Your nested loops (iterating x up to 100 million, then y from 1 to x-1) result in ~5e15 operations for order=1e8. Even modern hardware can't process that many operations in days, let alone minutes.

The Mathematical Fix: Euler's Totient Function φ(x) #

Project Euler Problem 351 counts obscured green points in a hexagonal grid, and the key insight ties directly to Euler's Totient Function:

• φ(x) counts integers from 1 to x-1 that are coprime with x.
• The number of reducible fractions (obscured points) for ring x is x - φ(x).

The problem's final total formula simplifies to:

total = 6 * (sum_{x=2 to order} (x - φ(x)) + order - 1)

This reduces our work to efficiently computing the sum of x - φ(x) using a sieve algorithm.

Optimized Implementation #

We'll use a linear sieve (Euler sieve) to compute φ(x) for all x up to 1e8 in O(n log log n) time—this is feasible in Python with moderate memory (a list of 1e8 integers takes ~400MB, which fits in most modern systems).

Here's the optimized code:

def compute_euler_phi(max_n):
    phi = list(range(max_n + 1))
    primes = []
    for i in range(2, max_n + 1):
        if phi[i] == i:  # i is a prime number
            primes.append(i)
            phi[i] = i - 1
        for p in primes:
            if i * p > max_n:
                break
            if i % p == 0:
                phi[i * p] = phi[i] * p
                break
            else:
                phi[i * p] = phi[i] * (p - 1)
    return phi

order = 100000000
phi = compute_euler_phi(order)

# Calculate sum of obscured points per ring
sum_obscured = sum(x - phi[x] for x in range(2, order + 1))

# Apply the problem's final formula
total = 6 * (sum_obscured + order - 1)
print(total)

Why This Works #

• Linear Sieve: This algorithm efficiently computes φ(x) by iterating through each number and updating φ values for prime multiples, avoiding redundant calculations. It's far faster than naive methods.
• Reduced Complexity: O(n log log n) means the sieve will run in minutes (not days) for n=1e8, depending on your hardware. The final sum operation is trivial compared to the sieve.

Additional Tips #

• If memory is tight, you can optimize the sieve to use more compact data types, but a standard list works for most systems with 8GB+ RAM.
• Avoid running other memory-heavy programs while the sieve runs—swapping to disk will drastically slow down the process.

内容的提问来源于stack exchange，提问作者S. Argentina