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$?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
There are several methods to find the factors of a number n :
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.