Efficiently determine every factor of a given natural number
def primeFactor(n):
    ''' Generates prime factors of n'''
    if n &lt;= 1: return
    prime = next((x for x in range(2, math.ceil(math.sqrt(n))+1) if n%x == 0), n)
    yield prime
    yield from primeFactor(n//prime)



For a start, consider that after yielding prime this can never yield a number less than prime, but the recursive call still starts again from 2. So one optimisation would be

def primeFactor(n):
    ''' Generates prime factors of n'''
    return primeFactorInner(n, 2)

def primeFactorInner(n, min):
    if n &lt; min: return
    prime = next((x for x in range(min, math.ceil(math.sqrt(n))+1) if n%x == 0), n)
    yield prime
    yield from primeFactorInner(n//prime, prime)




Next, that range with an implicit step of 1 is a bit overkill. Once you've finished returning 2s you could just step through odd numbers. At this point I'm tempted to say that it would be convenient to change the return value to already do the grouping, and have an auxiliary method to get the power of a prime in n.

def primePower(n, p): return 0 if n%p &gt; 0 else 1 + primePower(n//p, p)


Then we can write

def primeFactorInner(n, min):
    if n &lt; min: return
    if min == 2:
        a = primePower(n, 2)
        if a &gt; 0:
            yield (2, a)
            yield from primeFactorInner(n // (2 ** a), 3)
            return
    prime = next((x for x in range(min, math.ceil(math.sqrt(n))+1, 2) if n%x == 0), n)
    a = primePower(n, prime)
    yield (prime, a)
    yield from primeFactorInner(n // (prime ** a), prime + 2)




Now, if we carry that argument to extremes we would only want to loop over primes. So we could split into two phases:

for p in enumeratePrimes(math.floor(sqrt(n)) + 1):
    a = primePower(n, p)
    if (a &gt; 0):
        yield (p, a)
        n = n // (p ** a)
        if n == 1:
            # Early abort
            return
if n &gt; 1:
    yield (n, 1)


enumeratePrimes would probably best be implemented with a simple sieve.




  I want it to return the factors in ascending order, without
  duplicates. Originally, I was hoping I'd be able to have the entire
  thing be a lazy function (no eager evaluation at all). Unfortunately,
  I haven't been able to figure out a good way to do this.


The short answer is a priority queue. Initially you insert 1. When you pop and yield a factor, you push certain multiples of the factor. The mildly interesting part is ensuring that you only push each number once. I've found the Java code where I did a variant on this, and ported it to Python:

import heapq

def divisors(n):
    primes = [(1, 1)] + list(primeFactors(n))
    q = [(1, 0, 1)]
    while len(q) &gt; 0:
        # d is the divisor
        # i is the index of its largest "prime" in primes
        # a is the exponent of that "prime"
        (d, i, a) = heapq.heappop(q)
        yield d
        if a &lt; primes[i][1]:
            heapq.heappush(q, (d * primes[i][0], i, a + 1))
        if i + 1 &lt; len(primes):
            heapq.heappush(q, (d * primes[i + 1][0], i + 1, 1))
            # The condition i &gt; 0 is to avoid duplicates arising because
            # d == d // primes[0][0]
            if i &gt; 0 and a == 1:
                heapq.heappush(q, (d // primes[i][0] * primes[i + 1][0], i + 1, 1))


I'm not really a Pythonista, so although I suspect that you can make this even lazier by avoiding the list(), I'll leave that to someone who knows the language better than me.