title: Find the largest divisor of N that is less than sqrt(N)
body: <p>Actually, given N a (possibly very large) even integer, I want to find N = F * R where gcd(F,R) = 1, F>R, and F is as small as possible (since I'll be completely factoring F). The heart of the problem is finding the largest divisor R where R &lt; sqrt(N).</p>
  
  <p><em>For example, N=36 should give F=9 and R=4. Notice that R is not necessarily prime, or a prime power. Note that I am NOT factoring N. The only restriction on F and R is that they are relatively prime.</em></p>
  
  <p>This is my quick and naive version, which is working:</p>
  
  <pre><code>def factor_partial(N):
      for R in xrange(int(math.sqrt(N)),1,-1):
          if N%R == 0 and gcd(R,N/R) == 1:
              return N/R, R
  </code></pre>
  
  <p>Another way I imagine doing it is by finding the divisors in increasing order, and removing any multiples of nondivisors along the way. Something like:</p>
  
  <pre><code>def factor_partial(N):
      i = range(2, int(sqrt(N)) + 1)
      while i:
          if N % i[0] != 0:
              remove_multiples(i, i[0]) #without removing i[0]
          else:
              if gcd(i[0], N/i[0]) == 1:
                  R = i[0]
          i.pop(0) #remove i[0]
  
      return N/R, R
  </code></pre>
  
  <p>I think this will be slow and memory intensive, but perhaps if <code>i</code> is instead a generator it could be efficient.  I haven't used generators much.</p>
  
  <p>Can I improve the first version? Is the second version viable (how would I do it)? Is there a completely different method that is better?</p>
  
  <p><em>Looking for answers in python, c, or pseudocode.</em></p>
  
  <hr>
  
  <p>This is for a project for a class on number theory. I'm implementing a primality test based on <a href="http://en.wikipedia.org/wiki/Pocklington_primality_test" rel="nofollow">Pocklington</a>. While I need a factorization algorithm, we haven't studied any and I'm probably not going to use one such as the quadratic sieve which is outside the scope of my class. I'm looking for specific help with the question posed.</p>