1
$\begingroup$

The title says it all. On my homework I am tasked with creating an algorithm that determines whether or not a natural number n can be written as the sum of two squares.

The only stipulation I am given is that I have access to (theoretically) a computer which will quickly tell me if a number k is a perfect square.

I really am just stuck on how to go about doing this, so even just a small hint in the right direction would be appreciated!

  • 0
    Whoop$s$, thought I $s$earched far and wide before asking. Sorry about that.2012-09-11

1 Answers 1

0

From the description, I guess you're supposed to brute-force it:

a=0 while true do    b=n-a^2    if b<0 return false    if b is a perfect square return true    a=a+1 end 
  • 0
    It might not be a great saving, but we could also divide by any square factors first, since they have no effect on representability by a sum of$2$squares. e.g. if $n\equiv 0 \pmod{4}$, then replace $n$ by $n/4$.2012-09-11