unix - 查找给定范围内毕达哥拉斯三元组的数量

Question

我正在尝试编写一个程序，用于打印给定范围 N 的毕达哥拉斯三元组 (a^2 + b^2 = c^2)，其中 a<=b<=c<=N。

#include <stdio.h>

int main()
{

  int a = 0, b = 0, c = 0, N, T,c2;

  scanf("%d", &T);

  while(T--)
  {
    int counter = 0;
    scanf("%d", &N);
   {
     for (c = 0; c <=N; c++)
     {
       for (b = 0; b < c; b++)
       {
          for (a = 0; a < b; a++)
          {
             c2 = c*c;
            if (a*a + b*b == c2 )
            //if(sqrt (pow(a,2) + pow(b,2)) == c) 
            {
                ++counter;
                 printf("\n %d , %d, %d \n",a,b,c);   }
            }
         }
      }
   }
   printf("%d\n", counter);

  }
  return 0;
}

这对于 N<1000 非常有效。对于更高的 N，例如 10000，这需要很多时间。 有没有更好的方法来优化这个程序或任何更好的算法而不是蛮力，以便花费更少的时间来计算更高的 N ？

Answer 1

根据数论，毕达哥拉斯三元组由 (2pq, p^2-q^2, p^2+q^2) 参数化。您可以枚举这些，并在 c > N 时中止。这当然是最佳选择，因为您执行的计算次数与三元组的数量一样多...