# Greatest Divisor less than root

Given a non-square composite number $n$, we know there exists a (prime) divisor $p < \sqrt n$. So there must exists a maximal divisor $m$ with the property: $m < \sqrt n$. A naive way of computing $m$ would be to take check the values: $$\lfloor \sqrt n \rfloor - 1, \lfloor \sqrt n \rfloor - 2, \lfloor \sqrt n \rfloor - 3, ...$$and select the first that divides $n$. Are there more efficient ways of finding $m$?

-
Fermat factorisation is more efficient than that. –  Daniel Fischer Dec 30 '13 at 11:00
Being able to find the greatest factor smaller than the square root is equivalent to being able to factor the number fully; so your best bet is factoring the number as (the other Peter) pointed out below. –  Peter Košinár Dec 30 '13 at 16:13

There are several methods to find the factors of a number n :

• Pollard-rho-method (works well for small factors)
• p-1-method and p+1-method (work well if n has a prime factor such that p-1 or p+1 have only small factors)

• Elliptic curve method (works well for factors upto about ${10}^{35}$

• quadratic sieve (the fastest method) works well for numbers up to 100 digits

If the complete factorization is found, it is easy to find the largest factor below the square-root.

Remark : It is eaven easier to test whether a number is prime or not.

-