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

Question

Can someone explain to me an efficient way of finding all the factors of a number in Python (2.7)?

I can create an algorithm to do this, but I think it is poorly coded and takes too long to produce a result for a large number.

Answer 1

from functools import reduce

def factors(n):
    return set(reduce(
        list.__add__,
        ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

This will return all of the factors, very quickly, of a number n.

Why square root as the upper limit?

sqrt(x) * sqrt(x) = x. So if the two factors are the same, they're both the square root. If you make one factor bigger, you have to make the other factor smaller. This means that one of the two will always be less than or equal to sqrt(x), so you only have to search up to that point to find one of the two matching factors. You can then use x // fac1 to get fac2.

The reduce(list.__add__, ...) is taking the little lists of [fac1, fac2] and joining them together in one long list.

The [i, n//i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0 returns a pair of factors if the remainder when you divide n by the smaller one is zero (it doesn't need to check the larger one too; it just gets that by dividing n by the smaller one.)

The set(...) on the outside is getting rid of duplicates, which only happens for perfect squares. For n = 4, this will return 2 twice, so set gets rid of one of them.

Answer 2

The solution presented by @agf is great, but one can achieve ~50% faster run time for an arbitrary odd number by checking for parity. As the factors of an odd number always are odd themselves, it is not necessary to check these when dealing with odd numbers.

I've just started solving Project Euler puzzles myself. In some problems, a divisor check is called inside two nested for loops, and the performance of this function is thus essential.

Combining this fact with agf's excellent solution, I've ended up with this function:

from functools import reduce
from math import sqrt
def factors(n):
        step = 2 if n%2 else 1
        return set(reduce(list.__add__,
                    ([i, n//i] for i in range(1, int(sqrt(n))+1, step) if n % i == 0)))

However, on small numbers (~ < 100), the extra overhead from this alteration may cause the function to take longer.

I ran some tests in order to check the speed. Below is the code used. To produce the different plots, I altered the X = range(1,100,1) accordingly.

import timeit
from math import sqrt
from matplotlib.pyplot import plot, legend, show

def factors_1(n):
    step = 2 if n%2 else 1
    return set(reduce(list.__add__,
                ([i, n//i] for i in range(1, int(sqrt(n))+1, step) if n % i == 0)))

def factors_2(n):
    return set(reduce(list.__add__,
                ([i, n//i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0)))

X = range(1,100000,1000)
Y = []
for i in X:
    f_1 = timeit.timeit('factors_1({})'.format(i), setup='from __main__ import factors_1', number=10000)
    f_2 = timeit.timeit('factors_2({})'.format(i), setup='from __main__ import factors_2', number=10000)
    Y.append(f_1/f_2)
plot(X,Y, label='Running time with/without parity check')
legend()
show()

X = range(1,100,1)

No significant difference here, but with bigger numbers, the advantage is obvious:

X = range(1,100000,1000) (only odd numbers)

X = range(2,100000,100) (only even numbers)

X = range(1,100000,1001) (alternating parity)

Answer 3

There is an industry-strength algorithm in SymPy called factorint:

>>> from sympy import factorint
>>> factorint(2**70 + 3**80) 
{5: 2,
 41: 1,
 101: 1,
 181: 1,
 821: 1,
 1597: 1,
 5393: 1,
 27188665321L: 1,
 41030818561L: 1}

This took under a minute. It switches among a cocktail of methods. See the documentation linked above.

Given all the prime factors, all other factors can be built easily.

---

Note that even if the accepted answer was allowed to run for long enough (i.e. an eternity) to factor the above number, for some large numbers it will fail, such the following example. This is due to the sloppy int(n**0.5). For example, when n = 10000000000000079**2, we have

>>> int(n**0.5)
10000000000000078L

Since 10000000000000079 is a prime, the accepted answer's algorithm will never find this factor. Note that it's not just an off-by-one; for larger numbers it will be off by more. For this reason it's better to avoid floating-point numbers in algorithms of this sort.

Answer 4

agf's answer is really quite cool. I wanted to see if I could rewrite it to avoid using reduce(). This is what I came up with:

import itertools
flatten_iter = itertools.chain.from_iterable
def factors(n):
    return set(flatten_iter((i, n//i) 
                for i in range(1, int(n**0.5)+1) if n % i == 0))

I also tried a version that uses tricky generator functions:

def factors(n):
    return set(x for tup in ([i, n//i] 
                for i in range(1, int(n**0.5)+1) if n % i == 0) for x in tup)

I timed it by computing:

start = 10000000
end = start + 40000
for n in range(start, end):
    factors(n)

I ran it once to let Python compile it, then ran it under the time(1) command three times and kept the best time.

• reduce version: 11.58 seconds
• itertools version: 11.49 seconds
• tricky version: 11.12 seconds

Note that the itertools version is building a tuple and passing it to flatten_iter(). If I change the code to build a list instead, it slows down slightly:

• iterools (list) version: 11.62 seconds

I believe that the tricky generator functions version is the fastest possible in Python. But it's not really much faster than the reduce version, roughly 4% faster based on my measurements.

Answer 5

Here's an alternative to @agf's solution which implements the same algorithm in a more pythonic style:

def factors(n):
    return set(
        factor for i in range(1, int(n**0.5) + 1) if n % i == 0
        for factor in (i, n//i)
    )

This solution works in both Python 2 and Python 3 with no imports and is much more readable. I haven't tested the performance of this approach, but asymptotically it should be the same, and if performance is a serious concern, neither solution is optimal.

Answer 6

For n up to 10**16 (maybe even a bit more), here is a fast pure Python 3.6 solution,

from itertools import compress

def primes(n):
    """ Returns  a list of primes < n for n > 2 """
    sieve = bytearray([True]) * (n//2)
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = bytearray((n-i*i-1)//(2*i)+1)
    return [2,*compress(range(3,n,2), sieve[1:])]

def factorization(n):
    """ Returns a list of the prime factorization of n """
    pf = []
    for p in primeslist:
      if p*p > n : break
      count = 0
      while not n % p:
        n //= p
        count += 1
      if count > 0: pf.append((p, count))
    if n > 1: pf.append((n, 1))
    return pf

def divisors(n):
    """ Returns an unsorted list of the divisors of n """
    divs = [1]
    for p, e in factorization(n):
        divs += [x*p**k for k in range(1,e+1) for x in divs]
    return divs

n = 600851475143
primeslist = primes(int(n**0.5)+1) 
print(divisors(n))

Answer 7

An alternative approach to agf's answer:

def factors(n):    
    result = set()
    for i in range(1, int(n ** 0.5) + 1):
        div, mod = divmod(n, i)
        if mod == 0:
            result |= {i, div}
    return result

Answer 8

The simplest way of finding factors of a number:

def factors(x):
    return [i for i in range(1,x+1) if x%i==0]

Answer 9

I've tried most of these wonderful answers with timeit to compare their efficiency versus my simple function and yet I constantly see mine outperform those listed here. I figured I'd share it and see what you all think.

def factors(n):
    results = set()
    for i in xrange(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            results.add(i)
            results.add(int(n/i))
    return results

As it's written you'll have to import math to test, but replacing math.sqrt(n) with n**.5 should work just as well. I don't bother wasting time checking for duplicates because duplicates can't exist in a set regardless.

Answer 10

I have recently developed a new approach for integer factorization, called Smooth Subsum Search (SSS). Here is my implementation in Python: https://github.com/sbaresearch/smoothsubsumsearch

It can factor 30-digit numbers in around 0.2 seconds, 40-digit numbers in around 2 seconds, 50-digit numbers in around 30 seconds, 60-digit numbers in around 200 seconds and 70-digit numbers in around 3000 seconds. Compared to the Self-Initializing Quadratic Sieve implementation in sympy, which is the most efficient Quadratic Sieve implementation in Python that I could find, it runs around 5 to 7 times faster. SSS is described in great detail in: https://arxiv.org/abs/2301.10529

Answer 11

Further improvement to afg & eryksun's solution. The following piece of code returns a sorted list of all the factors without changing run time asymptotic complexity:

    def factors(n):    
        l1, l2 = [], []
        for i in range(1, int(n ** 0.5) + 1):
            q,r = n//i, n%i     # Alter: divmod() fn can be used.
            if r == 0:
                l1.append(i) 
                l2.append(q)    # q's obtained are decreasing.
        if l1[-1] == l2[-1]:    # To avoid duplication of the possible factor sqrt(n)
            l1.pop()
        l2.reverse()
        return l1 + l2

Idea: Instead of using the list.sort() function to get a sorted list which gives nlog(n) complexity; It is much faster to use list.reverse() on l2 which takes O(n) complexity. (That's how python is made.) After l2.reverse(), l2 may be appended to l1 to get the sorted list of factors.

Notice, l1 contains i-s which are increasing. l2 contains q-s which are decreasing. Thats the reason behind using the above idea.

Answer 12

Here is another alternate without reduce that performs well with large numbers. It uses sum to flatten the list.

def factors(n):
    return set(sum([[i, n//i] for i in xrange(1, int(n**0.5)+1) if not n%i], []))

Answer 13

Be sure to grab the number larger than sqrt(number_to_factor) for unusual numbers like 99 which has 3*3*11 and floor sqrt(99)+1 == 10.

import math

def factor(x):
  if x == 0 or x == 1:
    return None
  res = []
  for i in range(2,int(math.floor(math.sqrt(x)+1))):
    while x % i == 0:
      x /= i
      res.append(i)
  if x != 1: # Unusual numbers
    res.append(x)
  return res

Answer 14

Here is an example if you want to use the primes number to go a lot faster. These lists are easy to find on the internet. I added comments in the code.

# http://primes.utm.edu/lists/small/10000.txt
# First 10000 primes

_PRIMES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 
        31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 
        73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 
        127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 
        179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 
        233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 
        283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 
        353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 
        419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 
        467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 
        547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 
        607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 
        661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 
        739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 
        811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 
        877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 
        947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 
# Mising a lot of primes for the purpose of the example
)


from bisect import bisect_left as _bisect_left
from math import sqrt as _sqrt


def get_factors(n):
    assert isinstance(n, int), "n must be an integer."
    assert n > 0, "n must be greather than zero."
    limit = pow(_PRIMES[-1], 2)
    assert n <= limit, "n is greather then the limit of {0}".format(limit)
    result = set((1, n))
    root = int(_sqrt(n))
    primes = [t for t in get_primes_smaller_than(root + 1) if not n % t]
    result.update(primes)  # Add all the primes factors less or equal to root square
    for t in primes:
        result.update(get_factors(n/t))  # Add all the factors associted for the primes by using the same process
    return sorted(result)


def get_primes_smaller_than(n):
    return _PRIMES[:_bisect_left(_PRIMES, n)]

Answer 15

a potentially more efficient algorithm than the ones presented here already (especially if there are small prime factons in n). the trick here is to adjust the limit up to which trial division is needed every time prime factors are found:

def factors(n):
    '''
    return prime factors and multiplicity of n
    n = p0^e0 * p1^e1 * ... * pk^ek encoded as
    res = [(p0, e0), (p1, e1), ..., (pk, ek)]
    '''

    res = []

    # get rid of all the factors of 2 using bit shifts
    mult = 0
    while not n & 1:
        mult += 1
        n >>= 1
    if mult != 0:
        res.append((2, mult))

    limit = round(sqrt(n))
    test_prime = 3
    while test_prime <= limit:
        mult = 0
        while n % test_prime == 0:
            mult += 1
            n //= test_prime
        if mult != 0:
            res.append((test_prime, mult))
            if n == 1:              # only useful if ek >= 3 (ek: multiplicity
                break               # of the last prime) 
            limit = round(sqrt(n))  # adjust the limit
        test_prime += 2             # will often not be prime...
    if n != 1:
        res.append((n, 1))
    return res

this is of course still trial division and nothing more fancy. and therefore still very limited in its efficiency (especially for big numbers without small divisors).

this is python3; the division // should be the only thing you need to adapt for python 2 (add from __future__ import division).

Answer 16

I found a simple solution using cypari library in python. Here's a link!

import cypari
def get_divisors(n):
   divisors = cypari.pari('divisors({})'.format(n))
   return divisors
print(get_divisors(24))

output

[1, 2, 3, 4, 6, 8, 12, 24]

Answer 17

If you don't want to use any libraries, then I think this is the easiest way to do it:

def factors(n):
    l = [] # empty list
    # appending the factors in the list
    for i in range(1,n+1):
        if n%i==0:
            l.append(i)
    return l

Answer 18

While the question says Python (2.7), people may be interested in this simple solution using Numpy.

import numpy as np

t=np.arange(2,n,1)
t[n%t==0]

This will not return 1 nor the number itself n. So it will return an empty array if n is prime.

Answer 19

I'm a little surprised I couldn't find a simple implementation for integer prime factorization in the form (p1 ** e1) * (p2 ** e2) ..., so I decided to write my own.

from collections import defaultdict
from itertools import count

def factorize(n):
    factors = defaultdict(int)
    for i in count(2):
        while n % i == 0:
            factors[i] += 1
            n /= i

        if n == 1:
            return factors

This function returns a dictionary where the keys are the prime factors, and the values are the exponents. So for example:

>>> factorize(608)
defaultdict(<class 'int'>, {2: 5, 19: 1})
>>> factorize(1152)
defaultdict(<class 'int'>, {2: 7, 3: 2})
>>> factorize(1088)
defaultdict(<class 'int'>, {2: 6, 17: 1})

This is obviously not the most efficient implementation — for one it iterates over the whole set of natural numbers, instead of going straight for the primes — but it's good enough for relatively small values, and simple enough that it can be easily understood.

Answer 20

Using set(...) makes the code slightly slower, and is only really necessary for when you check the square root. Here's my version:

def factors(num):
    if (num == 1 or num == 0):
        return []
    f = [1]
    sq = int(math.sqrt(num))
    for i in range(2, sq):
        if num % i == 0:
            f.append(i)
            f.append(num/i)
    if sq > 1 and num % sq == 0:
        f.append(sq)
        if sq*sq != num:
            f.append(num/sq)
    return f

The if sq*sq != num: condition is necessary for numbers like 12, where the square root is not an integer, but the floor of the square root is a factor.

Note that this version doesn't return the number itself, but that is an easy fix if you want it. The output also isn't sorted.

I timed it running 10000 times on all numbers 1-200 and 100 times on all numbers 1-5000. It outperforms all the other versions I tested, including dansalmo's, Jason Schorn's, oxrock's, agf's, steveha's, and eryksun's solutions, though oxrock's is by far the closest.

Answer 21

I was pretty surprised when I saw this question that no one used numpy even when numpy is way faster than python loops. By implementing @agf's solution with numpy and it turned out at average 8x faster. I belive that if you implemented some of the other solutions in numpy you could get amazing times.

Here is my function:

import numpy as np
def b(n):
    r = np.arange(1, int(n ** 0.5) + 1)
    x = r[np.mod(n, r) == 0]
    return set(np.concatenate((x, n / x), axis=None))   

Notice that the numbers of the x-axis are not the input to the functions. The input to the functions is 2 to the the number on the x-axis minus 1. So where ten is the input would be 2**10-1 = 1023

Answer 22

your max factor is not more than your number, so, let's say

def factors(n):
    factors = []
    for i in range(1, n//2+1):
        if n % i == 0:
            factors.append (i)
    factors.append(n)

    return factors

voilá!

Answer 23

 import math

    '''
    I applied finding prime factorization to solve this. (Trial Division)
    It's not complicated
    '''


    def generate_factors(n):
        lower_bound_check = int(math.sqrt(n))  # determine lowest bound divisor range [16 = 4]
        factors = set()  # store factors
        for divisors in range(1, lower_bound_check + 1):  # loop [1 .. 4]
            if n % divisors == 0:
                factors.add(divisors)  # lower bound divisor is found 16 [ 1, 2, 4]
                factors.add(n // divisors)  # get upper divisor from lower [ 16 / 1 = 16, 16 / 2 = 8, 16 / 4 = 4]
        return factors  # [1, 2, 4, 8 16]


    print(generate_factors(12)) # {1, 2, 3, 4, 6, 12} -> pycharm output

 Pierre Vriens hopefully this makes more sense. this is an O(nlogn) solution. 

Answer 24

We can use the following lambda function,

factor = lambda x:[(ele,x/ele) for ele in range(1,x//2+1) if x%ele==0 ]

factor(10)

output: [(1, 10.0), (2, 5.0), (5, 2.0)]

This function returns all the factors of the given number in list.

Answer 25

Use something as simple as the following list comprehension, noting that we do not need to test 1 and the number we are trying to find:

def factors(n):
    return [x for x in range(2, n//2+1) if n%x == 0]

In reference to the use of square root, say we want to find factors of 10. The integer portion of the sqrt(10) = 4 therefore range(1, int(sqrt(10))) = [1, 2, 3, 4] and testing up to 4 clearly misses 5.

Unless I am missing something I would suggest, if you must do it this way, using int(ceil(sqrt(x))). Of course this produces a lot of unnecessary calls to functions.

Answer 26

I think for readability and speed @oxrock's solution is the best, so here is the code rewritten for python 3+:

def num_factors(n):
    results = set()
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0: results.update([i,int(n/i)])
    return results

Answer 27

loop until you find a duplicate in x or v of the tuple where x is the denominator and v is the resultant.

number=30
tuple_list=[]
for i in np.arange(1,number):
    if number%i==0:
         other=int(number/i)
         if any([(x,v) for (x,v) in tuple_list if (i==x) or (i==v)])==True:
             break
         tuple_list.append((i,other))
    
 flattened = [item for sublist in tuple_list for item in sublist]              
 print(sorted(flattened))

output

 [1, 2, 3, 5, 6, 10, 15, 30]

Answer 28

Considering the number is positive integer, you may use this approach:

number = int(input("Enter a positive number to find factors: "))
factor = [num for num in range(1,number+1) if number % num == 0]
for fac in factor: print(f"{fac} is a factor of {number}")

Answer 29

Python 3.5 added a gcd() function in the standard math module:

math.gcd(*integers)

Return the greatest common divisor of the specified integer arguments. If any of the arguments is nonzero, then the returned value is the largest positive integer that is a divisor of all arguments. If all arguments are zero, then the returned value is 0. gcd() without arguments returns 0.

Answer 30

I reckon this is the simplest way to do that:

    x = 23

    i = 1
    while i <= x:
      if x % i == 0:
        print("factor: %s"% i)
      i += 1