

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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$?

share|cite|improve this question
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
up vote 0 down vote accepted

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.

share|cite|improve this answer

Your Answer


