当 a、b 或 c <= 1000 时，更快地找到所有毕达哥拉斯四元组

Question

我正在尝试获取所有毕达哥拉斯四元组：

a^2 + b^2 + c^2 = d^2 when a, b, c <= 1000,

我的代码生成了所有这些 (85490)，但大约需要 10 分钟。

我正在尝试减少执行时间。我怎样才能缩短执行时间？有什么建议吗

这是我的代码。

   static int isSquare(int n)
   {
      int m = (int) Math.sqrt(n);

      return m * m == n ? m : 0;
   }

   static List<List<Integer>> allQuadraples = new ArrayList<>();

   static int findQuadraples(int range)
   {
      int total = 0;

      for (int a = 1; a <= range; a++)
         for (int b = 1; b <= range; b++)
            for (int c = 1; c <= range; c++)
            {
               int sum = a * a + b * b + c * c;

               int d = isSquare(sum);

               if (d != 0) // a possible Quadruple
               {
                  List<Integer> oneQuadraple = new ArrayList<>(Arrays.asList(a, b, c, d));
                  Collections.sort(oneQuadraple); // sorting before insertion for comparing later
                  if (!allQuadraples.contains(oneQuadraple))
                  {
                     System.out.println(oneQuadraple);
                     allQuadraples.add(oneQuadraple);
                     total++;
                  }
               }
            }

      return total;
   }

Answer 1

所以，如果您仍然需要存储所有四元组，那么这就是新函数，（感谢 Damien）。

只用了 1.5 秒。用于查找和存储所有 85490.

   static int findQuadraples(int range)
   {
      int total = 0;

      for (int a = 1; a <= range; a++)
         for (int b = a; b <= range; b++)
            for (int c = b; c <= range; c++)
            {
               int sum = a * a + b * b + c * c;
               int d = isSquare(sum);

               if (d != 0) // a possible Quadruple
               {
                  //System.out.println(Arrays.asList(a, b, c, d));
                  allQuadraples.add(Arrays.asList(a, b, c, d));
                  total++;
               }
            }

      return total;
   }

如果不保存到 ArrayList，则需要 1.3 秒。

Answer 2

这是一种使用较慢语言的不同方法。即匹配 a^2 + b^2 和 d^2 - c^2。操作速度较慢，但算法是 O(n^2) 而不是 O(n^3).

在 Python 这在我的笔记本电脑上花费了 < 1.3 秒。

#! /usr/bin/env python3
limit = 1000

square_differences = {}
for c in range(limit, 0, -1):
    for d in range (c+1, 2*c):
        diff = d*d - c*c
        if 3*limit*limit< diff:
            break
        elif diff not in square_differences:
            square_differences[diff] = []
        square_differences[diff].append((c, d))

quads = []
for a in range(1, limit+1):
    for b in range(a, limit+1):
        s = a*a + b*b
        if s in square_differences:
            for c, d in square_differences[s]:
                if c < b:
                    break
                else:
                    quads.append((a, b, c, d))

print(len(quads))

当 a、b 或 c <= 1000 时，更快地找到所有毕达哥拉斯四元组

Finding all the Pythagorean quadruples faster when a, b or c <= 1000

java

algorithm

time-complexity

pythagorean