Why don't you try generating all squares and then search the array for n.
You'll have 65535 squares at max. So, using binary search you could determine, whteher sqrt(n) is an integer or not. The array won't be that big, but it could be not the fastest way.
P.S I haven't solved the problem myself, so I'm just giving some ideas that popped up my mind.