Look at wikipedia link: http://en.wikipedia.org/wiki/Fermat%27s_factorization_method and look for basic method that is written there, where you have while loop.
For every loop you have to square number and if it is not right you add 1 and go to the next number and square it again.
We all know that Differrence between square numbers is sum of consecutive odd numbers.
example: 1 + 3 + 5 = 9 or 1 + 3 + 5 + 7 = 16 and so on
So why dont we memorize the number we just got squared/ckecked and then just add another next odd integer for next square number? Is that less compute-time consuming?
And what about that improvement? And some other improvements on the Fermat factorization method : Let us not use it for even numbers (that is anyway) and for numbers with digit sum that equals 3,6,9.
In therms of digit sum of squares there are only for posibilities 1,4,7,9
I also found out that in case of equation of the diference of squares there is always digit sum number 9 involved!
So if I shorten story up there are only next squared digit sum cases possible for difference of squares equation: 1 = 1 - 9 ; 2 = 9 - 7 ; 4 = 4 - 9 ; 5 = 9 - 4 ; 7 = 7 - 9 ; 8 = 9 - 1 ;
Example: 341 => digit sum is 8, so the only possible way is 8 = 9 - 1. As you know digit sum 9 is 21 squared and digit sum 1 represents 10 squared. So we know how does bigger squared number look like and how does the smaller, so we can jump only to those squared numbers which are needed.