algorithm - 不同质数的乘积为完美平方的总和

给定:k个不同的素数说a1，a2，.....，ak

目标:将给定素数乘积写为理想平方和所需的最小理想平方数。

例子:
k = 2, a1 = 3, a2 = 5a1*a2 = 15 = 9 + 4 + 1 + 1，即4个完美平方
k = 3, a1 = 2, a2 = 5, a3 = 11a1*a2*a3 = 110 = 100 + 9 + 1，即3个完美平方和

我的算法

让p = a1*a2*...........*ak

counter = 0
while p != 0:
    find the largest perfect square <= p say z
    p = p-z
    counter = counter + 1
return counter

我已经通过几个示例对其进行了测试。对我来说，这似乎是正确的。但是根据几个例子来概括是不正确的。如何证明这一点(如果算法正确)？

最佳答案

解决方法正确吗？

实际上，在以下情况下，您的解决方案是错误的:

k = 1, a1 = 61 => Your result: 61 = 49 + 9 + 1 + 1 + 1 / Best Result: 61 = 36 + 25

k = 2, a1 = 2, a2 = 37 => Your result: 74 = 64 + 9 + 1 / Best Result: 74 = 49 + 25

使用勒让德三平方定理的解决方案

Legendre's Three-square Theorem是所有自然数n，但n是4^a (8b + 7)的形式，可以表示三个平方和。
还有Lagrange's Four-square Theorem，所有自然数都可以表示四个平方的和。

所以算法是:

计算n是否为4^a (8b + 7)的形式。您可以使用素数分解。如果是这样，答案是4。

计算n是否为平方数。如果是这样，答案是1.

计算n是否可以表示两个平方。如果是这样，答案是2。

如果1-3均为假，则答案为3。

您可以对O(sqrt(n))执行操作1，对O(log(n))执行操作2，对于O(sqrt(n) * log(n))执行操作3，因此总的时间复杂度为O(sqrt(n) * log(n))。

编辑:
由于n是一个不同的素积，因此不会出现平方数，因此不会出现情况2。
如果n mod 8 = 7，则出现情况1。