[dmdox]

If you're interested in investigating more, take a look at "Continued Fraction Factorization". This is essentially the first step of that more advanced algorithm.

From the continued fraction of √n, you get a series of best rational approximations a/b to √n. Each such approximation gives you:

a/b ~ √n

a² ~ b² n

The first approximation is a = floor(√n), b = 1

These approximations satisfy |a² - b² n| < 2 √n.

(this can be used for generating relations as input to Dixon's method)