What is the most efficient way of finding all the factors of a number in Python?

python

micro-optimization

generators

performance-tuning

byAlex Kataev·Mar 11, 2025

Efficiency in finding factors lies in the key principle of limiting the search space to sqrt(n). Here's a compact Python expression that does just that:

def optimal_factors(n):
    return sorted({i for i in range(1, int(n**0.5) + 1) if n % i == 0 for j in (i, n//i)})

This single-pass approach detects small factors 'i' and concurrently captures their complementary factor 'n//i', thus identifying all factors up to n without excessive searches beyond the sqrt(n) boundary.

Tricks to boost your factors search function

While the simple function above is powerful, there are a few additional tricks to boost factor search, especially when handling large and odd numbers. Here's the arsenal:

Odds don't like even numbers: Add a parity check that halve the runtime as even multiples do not exist for odd dividends.

step = 2 if n % 2 else 1  # Ain't nobody got time for evens if we're odd
factors = {factor for i in range(1, int(n**0.5) + 1, step) for factor in (i, n//i) if n % i == 0}

Generators are memory-savers: For giant numbers, utilise generators. They yield factors as needed, saving memory.

def gen_factors(n):
    for i in range(1, int(n**0.5) + 1):  # We go up to the square root
        if n % i == 0:  # Is it a factor? Let's find out!
            yield i  # Ladies and gentlemen, we got one!
            if i != n // i:  # No need to yield twice if it's the square root
                yield n // i  # Here's the complementary factor

Dodge the floating-point bullet: Floating-point inaccuracies can creep into your calculations with large integers - so avoid where possible.
Prime factorization is the key: For superior performance consider SymPy's factorint - it uses futuristic algorithms and dynamically chooses the best method for the task.

Measure your code performance

Do not forget to benchmark your function:

Use timeit to assess execution time and compare different recipes. This will reinforce your confidence in your performance improvements.
When tweaking, keep in mind overhead. Like a well-intentioned friend who talks too much, overhead from things like generators or set conversions can hit smaller numbers harder.

And remember kids, micro-optimization might not be the hero you need, but the villain you get. Stick to readability and simplicity.

Exploit prime factorization

In scenarios where you need to factorize numerous numbers, think about building from primes:

Generate prime factors: Use efficient prime factorization algorithms to get the basic structure of your numbers.
Combine prime factors: Deriving other factors from these primes is a walk in the park - multiply them in different combinations.

Again, SymPy's factorint is your reliable comrade for prime factor calculation.

Compatibility is king, readability is queen

Aim to keep your code friendly across Python 2 and 3 for broader acceptability:

To ensure consistent division in Python 2, use from __future__ import division.
For a Pythonic and readable style, use list comprehensions and generators. They are smart and elegant, just like you.