algorithm - 如何检查给定数字 N, N^2 是否可以表示为两个非零整数的平方和？

Question

给定一个数 N，我如何确定 N^2 是否可以表示为两个非零整数的平方和。例如，如果 N=10，则 10^2 可以表示为 (6^2)+(8^2)。我读过这样的数字 N 可以表示为 4k+1 但即使是 9 也符合该表达式，但 81 不能表示为两个整数的平方和。执行此操作的正确方法是什么？

Answer 1

您想要的数字是毕达哥拉斯三元组的斜边(“c”值)，系列 A009000在 OEIS 中。那里的评论指出，当且仅当它可以被至少一个 4k+1 形式的素数整除时，它才是斜边。因此，您可以通过获取素数分解来检查一个数是否为斜边，然后查看这些素数中的任何一个在除以 4 时是否余数为 1。

在您的示例中，81 不合格，因为它唯一的质因数是 3。81 可以被 9 整除，但 9 不是质数。