Product of distinct prime numbers as a sum of perfect square
<p><strong>Given</strong>: k distinct prime numbers say a1, a2, ....., ak</p>

<p><strong>Objective</strong>: Minimum number of perfect squares required to write product of the given primes as a sum of perfect squares.</p>

<p>Examples:</p>

<p><code>k = 2, a1 = 3, a2 = 5</code>
<code>a1*a2 = 15 = 9 + 4 + 1 + 1</code> i.e sum 4 perfect squares</p>

<p><code>k = 3, a1 = 2, a2 = 5, a3 = 11</code>
<code>a1*a2*a3 = 110 = 100 + 9 + 1</code> i.e. sum 3 perfect squares</p>

<p>My Algorithm</p>

<p>let <code>p = a1*a2*...........*ak</code></p>

<pre><code>counter = 0
while p != 0:
    find the largest perfect square &lt;= p say z
    p = p-z
    counter = counter + 1
return counter
</code></pre>

<p>I have tested it for few examples. To me it seems to be correct. But it is incorrect to generalize on the basis of few examples. How to prove this(if algorithm is correct)?  </p>