This reminds me of something I read lo, these many years ago in

__Recreations in the Theory of Numbers__ The Queen of Mathematics Entertains

by ALBERT H. BEILER

which (three cheers for the Information Age!) may be found

here
In the chapter "Resolution" on factoring we find the following example:

*Since any odd integer in excess of unity can be represented as the difference of two squares, we must ultimately arrive at a square if we add squares to an unknown odd number. But if the unknown should happen to be a prime, then it may take many steps before the sum is a square so that this method had best be abandoned if results are not obtained within a reasonable number of trials. Thus, even for so small a number as 9839, one would have to exhaust almost half of Barlow's table of squares before finding that 9839+4919*^{2} = 4920^{2} or 9839 = (4920+4919)(4920-4919) = 9839ยท1, and that consequently 9839 is a prime.
OK, this is slightly cruder than Fermat's method (which is described just before), but only slightly. These simple methods become prohibitively laborious even for small numbers.