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

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

User · Answer

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  - gt  pycharm output   Pierre Vriens hopefully this makes more sense  this is an O nlogn  solution

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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  amp  1          mult    1         n  gt  gt   1     if mult    0          res append  2  mult        limit   round sqrt n       test prime   3     while test prime  lt   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  gt   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

User · Answer

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

User · Answer

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

User · Answer

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  gt  0   n must be greather than zero       limit   pow  PRIMES -1   2      assert n  lt   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

User · Answer

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

User · Answer

There is an industry-strength algorithm in SymPy called factorint    gt  gt  gt  from sympy import factorint  gt  gt  gt  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    gt  gt  gt  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

User · Answer

I reckon this is the simplest way to do that       x   23      i   1     while i  lt   x        if x   i    0          print  factor   s   i        i    1

User · Answer

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

User · Answer

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

User · Answer

Further improvement to afg  amp  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

User · Answer

import  dart math   generateFactorsOfN N       determine lowest bound divisor range   final lowerBoundCheck   sqrt N  toInt      var factors   Set lt int gt       stores factors            Lets take 16       4   sqrt 16       start from 1      4 inclusive      check mod 16   1    0   set 1   16   1        check mod 16   2    0   set 1   16   1    2    16   2        check mod 16   3    0   set 1   16   1    2    16   2   - gt  unchanged      check mod 16   4    0   set 1   16   1    2    16   2   4   16   4                                  set is used to remove duplicate                           case 4 and  16   4  both equal to 4       return factor set lt int gt    this isn t ordered          for var divisor   1  divisor  lt   lowerBoundCheck  divisor         if N   divisor    0         factors add divisor         factors add N    divisor         integer division              return factors

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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  lt  n for n  gt  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  gt  n   break       count   0       while not n   p          n     p         count    1       if count  gt  0  pf append  p  count       if n  gt  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

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

Examples related to python

Examples related to algorithm

Examples related to python-2.7

Examples related to performance

Examples related to factorization