如何提升欧拉计划第39题解决方案的效率？目标支持p≤1000

嘿，我完全懂你这种暴力法卡到崩溃的感受！欧拉计划第39题靠硬遍历确实效率太低，得换数学思路来提速——毕竟勾股数本身有成熟的生成公式，用这个来替代暴力枚举，分分钟就能搞定p≤1000的情况。

首先得回忆一下本原勾股数（a,b,c互质的直角三角形）的生成规则：

对于任意两个正整数m和n，满足m>n>0、m和n一奇一偶、m和n互质，那么可以生成一组本原勾股数：
a = m² - n²，b = 2mn，c = m² + n²
所有非本原的勾股数都是某个本原勾股数的整数倍（k倍，k≥2）

基于这个规则，我们不需要遍历所有可能的a、b、c，而是直接生成所有合法的勾股数，再统计它们的周长对应的解数。

1. 确定m的范围：本原勾股数的周长p₀ = a+b+c = 2m(m+n)。因为n>0，所以p₀ > 2m²。要让p₀ ≤1000，可得2m² ≤1000 → m ≤ √500 ≈22.36，所以m只需要从2遍历到22就行，范围极小！
2. 筛选合法的n：对每个m，遍历n从1到m-1，只保留满足两个条件的n：
   • m和n互质（用最大公约数gcd判断）
   • m和n一奇一偶（即m-n是奇数）
3. 统计周长的解数：对每个生成的本原勾股数，计算它的周长p₀，然后把p₀的所有k倍（k*p₀ ≤1000）对应的解数都加1（因为每个倍数都是一组非本原的解）。
4. 找解数最多的p：遍历统计数组，找出解数最大的p值。

import math

max_p = 1000
solution_counts = [0] * (max_p + 1)

# 遍历所有可能的m
for m in range(2, int((max_p // 2) ** 0.5) + 1):
    # 遍历所有小于m的n
    for n in range(1, m):
        # 检查m和n是否满足本原勾股数的条件
        if (m - n) % 2 == 1 and math.gcd(m, n) == 1:
            # 计算本原勾股数的周长，不用生成a,b,c，直接算更高效
            p0 = 2 * m * (m + n)
            # 统计所有p0的倍数
            k = 1
            while k * p0 <= max_p:
                solution_counts[k * p0] += 1
                k += 1

# 找到解数最多的p
max_count = max(solution_counts)
best_p = [p for p in range(1, max_p + 1) if solution_counts[p] == max_count][0]

print(f"当p≤1000时，解数最多的p是{best_p}，共有{max_count}组解")

暴力法的时间复杂度是O(p²)（对每个p遍历a和b），而这个数学方法的时间复杂度几乎是常数级：m最多22个，每个m对应的n最多21个，总本原勾股数只有几十组，再加上倍数统计，总操作数不到1000次，完全能在毫秒级出结果，别说1小时，1秒都用不了。

• 不用生成a、b、c，直接计算p₀=2m(m+n)，节省计算量
• 提前计算m的上限，避免无效循环
• 用math.gcd快速判断互质，比自己实现更高效

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