Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

1 Answer 1

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|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.