\\Fermat factoring algorithm
\\Usage: fermat(n), where n is an ODD positive integer
\\It will produce two factors of n, those being 1 and n
\\if and only if n is prime.
\\Practical only when n=ab where |a-b| is small compared to n
\\by Felipe Voloch



{
fermat(n,
         x,y,a)=a=floor(sqrt(n));x=a+1;y=floor(sqrt(x^2-n));
         if(n<=1||n%2==0,error("Invalid input"));
         if(n==a^2,print(n," is the square of ",a),
          if(n==x^2-y^2,print(n," is the product of ",x-y," and ",x+y),
           until(n==x^2-y^2,x=x+1;y=floor(sqrt(x^2-n));
            if(n==x^2-y^2,print(n," is the product of ",x-y," and ",x+y),
            )
           )
          )
         )
}