Fast Number Factorization in Python












6












$begingroup$


Here's my implementation to factorize a positive integer:



def is_prime(n):
if n == 1:
return False
if n % 2 == 0:
return False
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
return True


# @timeit
def prime_factors(n):
prime_factor_list =
while not n % 2:
prime_factor_list.append(2)
n //= 2
while not n % 3:
prime_factor_list.append(3)
n //= 3
i = 5
while n != 1:
if is_prime(i):
while not n % i:
prime_factor_list.append(i)
n //= i
i += 2

return prime_factor_list


How can I improve this code in speed and make it pythonic?










share|improve this question











$endgroup$








  • 1




    $begingroup$
    I think that the best way to do fast number factorization in python is just call an external library (which does not rely on Python iteration) such as sympy. See related answer on StackOverflow stackoverflow.com/questions/4643647/… ).
    $endgroup$
    – John Donn
    Mar 4 '16 at 9:54


















6












$begingroup$


Here's my implementation to factorize a positive integer:



def is_prime(n):
if n == 1:
return False
if n % 2 == 0:
return False
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
return True


# @timeit
def prime_factors(n):
prime_factor_list =
while not n % 2:
prime_factor_list.append(2)
n //= 2
while not n % 3:
prime_factor_list.append(3)
n //= 3
i = 5
while n != 1:
if is_prime(i):
while not n % i:
prime_factor_list.append(i)
n //= i
i += 2

return prime_factor_list


How can I improve this code in speed and make it pythonic?










share|improve this question











$endgroup$








  • 1




    $begingroup$
    I think that the best way to do fast number factorization in python is just call an external library (which does not rely on Python iteration) such as sympy. See related answer on StackOverflow stackoverflow.com/questions/4643647/… ).
    $endgroup$
    – John Donn
    Mar 4 '16 at 9:54
















6












6








6


3



$begingroup$


Here's my implementation to factorize a positive integer:



def is_prime(n):
if n == 1:
return False
if n % 2 == 0:
return False
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
return True


# @timeit
def prime_factors(n):
prime_factor_list =
while not n % 2:
prime_factor_list.append(2)
n //= 2
while not n % 3:
prime_factor_list.append(3)
n //= 3
i = 5
while n != 1:
if is_prime(i):
while not n % i:
prime_factor_list.append(i)
n //= i
i += 2

return prime_factor_list


How can I improve this code in speed and make it pythonic?










share|improve this question











$endgroup$




Here's my implementation to factorize a positive integer:



def is_prime(n):
if n == 1:
return False
if n % 2 == 0:
return False
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
return True


# @timeit
def prime_factors(n):
prime_factor_list =
while not n % 2:
prime_factor_list.append(2)
n //= 2
while not n % 3:
prime_factor_list.append(3)
n //= 3
i = 5
while n != 1:
if is_prime(i):
while not n % i:
prime_factor_list.append(i)
n //= i
i += 2

return prime_factor_list


How can I improve this code in speed and make it pythonic?







python performance primes






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Mar 4 '16 at 15:22









chepner

24315




24315










asked Mar 4 '16 at 6:26









user2305user2305

17825




17825








  • 1




    $begingroup$
    I think that the best way to do fast number factorization in python is just call an external library (which does not rely on Python iteration) such as sympy. See related answer on StackOverflow stackoverflow.com/questions/4643647/… ).
    $endgroup$
    – John Donn
    Mar 4 '16 at 9:54
















  • 1




    $begingroup$
    I think that the best way to do fast number factorization in python is just call an external library (which does not rely on Python iteration) such as sympy. See related answer on StackOverflow stackoverflow.com/questions/4643647/… ).
    $endgroup$
    – John Donn
    Mar 4 '16 at 9:54










1




1




$begingroup$
I think that the best way to do fast number factorization in python is just call an external library (which does not rely on Python iteration) such as sympy. See related answer on StackOverflow stackoverflow.com/questions/4643647/… ).
$endgroup$
– John Donn
Mar 4 '16 at 9:54






$begingroup$
I think that the best way to do fast number factorization in python is just call an external library (which does not rely on Python iteration) such as sympy. See related answer on StackOverflow stackoverflow.com/questions/4643647/… ).
$endgroup$
– John Donn
Mar 4 '16 at 9:54












5 Answers
5






active

oldest

votes


















6












$begingroup$

prime_factors()



The single greatest improvement to performance that you could make would be to remove the call to is_prime() altogether. If all factors smaller than i have been removed from n already, then i could not possibly be composite.



The next improvement you could make would be to turn prime_factors() into a generator. The function would no longer need to resize and recopy prime_factor_list whenever the list needs to grow beyond its estimated size. Furthermore, the caller could start making use of initial results before the entire factorization is finished.



Using three lines (i = 5, while n != 1, and i += 2) to structure the loop — something that would be succinctly written in C as a for (i = 5; n != 1; i += 2) header — is un-Pythonic. Such counting loops are usually better written using some kind of range(), xrange(), enumerate(), or something from itertools. Here, itertools.chain() and itertools.count() would be appropriate.



Without changing the spirit of your algorithm, I would write:



import itertools

def prime_factors(n):
for i in itertools.chain([2], itertools.count(3, 2)):
if n <= 1:
break
while n % i == 0:
n //= i
yield i


is_prime()



As mentioned above, you don't need is_prime() at all, if your only goal is to implement prime_factors().



However, if you wanted to implement is_prime() anyway, you could tighten it up a bit. My main recommendation would be to avoid performing the i * i multiplication with each iteration. You would probably be better off computing the $sqrt{n}$ limit just once.



Then, as with the other function, you should express the loop more Pythonically using range() or xrange(). Actually, you wouldn't need an explicit loop; you could use any() instead.



So, if we stick to your algorithm in spirit, we could tighten up the implementation like this:



def is_prime(n):
if n < 3 or n % 2 == 0:
return n == 2
else:
return not any(n % i == 0 for i in range(3, int(n**0.5 + 2), 2))





share|improve this answer











$endgroup$













  • $begingroup$
    using is_prime was really dumb. Good Observation.
    $endgroup$
    – user2305
    Mar 4 '16 at 10:51










  • $begingroup$
    @200_success @user2305 "If all factors smaller than i have been removed from n already, then i could not possibly be composite." i can and will be composite (it's just going through odd numbers, and most of them are composite). It's just that, if i is composite, it will not divide the remaining n, and I think that's what the OP was trying to skip. However, I do agree with removing the call to is_prime(): trying to avoid a O(1) operation with a O(log(n)) check is not exactly an optimization! :)
    $endgroup$
    – OxTaz
    Mar 4 '16 at 17:16












  • $begingroup$
    @200_success: you can break the loop if n < i * i and yield n as the largest prime factor.
    $endgroup$
    – Daniel
    Mar 6 '16 at 15:37



















4












$begingroup$

Your code is written fairly well, yet in is_prime you forgot to check whether the input integer is 2; just add this:



if n == 2:
return True


Also, for some negative integers is_prime returns True. I suggest you add the following statement to prune them away:



if n <= 1:
return False





share|improve this answer











$endgroup$





















    3












    $begingroup$

    prime_factors never calls is_prime with a number that's divisible by 2 or 3. is_prime could be faster if it used this knowledge. However, if is_prime will use this knowledge, then it may be a bit misleading in global scope. So you could move the definition of is_prime inside of prime_factors.



    Although the code is Pythonic alright, it would be more idiomatic to use a prime generator to get the next prime factor, instead of iterating from 5 upwards. Given a prime generator gen, the final loop of the code would become:



    while n != 1:
    prime = next(gen)
    while not n % prime:
    prime_factor_list.append(prime)
    n //= prime





    share|improve this answer









    $endgroup$





















      0












      $begingroup$

      Few additional thoughts to Fast Number Factorization in Python answer.



      is_prime()



      In case if you have multiple consequent calls you should use something like Sieve_of_Eratosthenes. If you will, time to generate sieve will depend on maximum value of number to factorize but total time will be reduces.



      prime_factors()



      There is one thing you miss in your code. Lets take prime number, let is be
      $ 10007 $ and multiply it by $ 2 $, we will receive $ 20014 $. Its factorization will be $ 20014 = 10007 times 2 $.



      Now lets analyze your prime_factors. You will find that $ 2 $ is prime divisor of $ 20014 $ and will continue to iterate through all prime numbers up to $ 10007 $ but actually you have to iterate up to square root of initial number, because if you cross this line and reminder still not equal $ 1 $ than it is prime.



      This trick can reduce time for such cases.



      As the result, you can assume that you need to generate sieve up to square root of highest number.






      share|improve this answer











      $endgroup$





















        0












        $begingroup$

        def print_factors(x):enter code here
        print("The factors of",x,"are:")enter code here
        for i in range(1, num+1):enter code here
        print()enter code here
        print(i,"#--->",end=' ')enter code here
        for j in range(1,i+1):enter code here
        if i % j == 0:enter code here
        print(j,end=', ')enter code here
        num = int(input("Enter a limit of the natural sequenced numbers: "))enter code here
        print_factors(num)enter code here






        share|improve this answer








        New contributor




        Vasanth is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.






        $endgroup$













          Your Answer





          StackExchange.ifUsing("editor", function () {
          return StackExchange.using("mathjaxEditing", function () {
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
          });
          });
          }, "mathjax-editing");

          StackExchange.ifUsing("editor", function () {
          StackExchange.using("externalEditor", function () {
          StackExchange.using("snippets", function () {
          StackExchange.snippets.init();
          });
          });
          }, "code-snippets");

          StackExchange.ready(function() {
          var channelOptions = {
          tags: "".split(" "),
          id: "196"
          };
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function() {
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled) {
          StackExchange.using("snippets", function() {
          createEditor();
          });
          }
          else {
          createEditor();
          }
          });

          function createEditor() {
          StackExchange.prepareEditor({
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: false,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          imageUploader: {
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          },
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          });


          }
          });














          draft saved

          draft discarded


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f121862%2ffast-number-factorization-in-python%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          5 Answers
          5






          active

          oldest

          votes








          5 Answers
          5






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          6












          $begingroup$

          prime_factors()



          The single greatest improvement to performance that you could make would be to remove the call to is_prime() altogether. If all factors smaller than i have been removed from n already, then i could not possibly be composite.



          The next improvement you could make would be to turn prime_factors() into a generator. The function would no longer need to resize and recopy prime_factor_list whenever the list needs to grow beyond its estimated size. Furthermore, the caller could start making use of initial results before the entire factorization is finished.



          Using three lines (i = 5, while n != 1, and i += 2) to structure the loop — something that would be succinctly written in C as a for (i = 5; n != 1; i += 2) header — is un-Pythonic. Such counting loops are usually better written using some kind of range(), xrange(), enumerate(), or something from itertools. Here, itertools.chain() and itertools.count() would be appropriate.



          Without changing the spirit of your algorithm, I would write:



          import itertools

          def prime_factors(n):
          for i in itertools.chain([2], itertools.count(3, 2)):
          if n <= 1:
          break
          while n % i == 0:
          n //= i
          yield i


          is_prime()



          As mentioned above, you don't need is_prime() at all, if your only goal is to implement prime_factors().



          However, if you wanted to implement is_prime() anyway, you could tighten it up a bit. My main recommendation would be to avoid performing the i * i multiplication with each iteration. You would probably be better off computing the $sqrt{n}$ limit just once.



          Then, as with the other function, you should express the loop more Pythonically using range() or xrange(). Actually, you wouldn't need an explicit loop; you could use any() instead.



          So, if we stick to your algorithm in spirit, we could tighten up the implementation like this:



          def is_prime(n):
          if n < 3 or n % 2 == 0:
          return n == 2
          else:
          return not any(n % i == 0 for i in range(3, int(n**0.5 + 2), 2))





          share|improve this answer











          $endgroup$













          • $begingroup$
            using is_prime was really dumb. Good Observation.
            $endgroup$
            – user2305
            Mar 4 '16 at 10:51










          • $begingroup$
            @200_success @user2305 "If all factors smaller than i have been removed from n already, then i could not possibly be composite." i can and will be composite (it's just going through odd numbers, and most of them are composite). It's just that, if i is composite, it will not divide the remaining n, and I think that's what the OP was trying to skip. However, I do agree with removing the call to is_prime(): trying to avoid a O(1) operation with a O(log(n)) check is not exactly an optimization! :)
            $endgroup$
            – OxTaz
            Mar 4 '16 at 17:16












          • $begingroup$
            @200_success: you can break the loop if n < i * i and yield n as the largest prime factor.
            $endgroup$
            – Daniel
            Mar 6 '16 at 15:37
















          6












          $begingroup$

          prime_factors()



          The single greatest improvement to performance that you could make would be to remove the call to is_prime() altogether. If all factors smaller than i have been removed from n already, then i could not possibly be composite.



          The next improvement you could make would be to turn prime_factors() into a generator. The function would no longer need to resize and recopy prime_factor_list whenever the list needs to grow beyond its estimated size. Furthermore, the caller could start making use of initial results before the entire factorization is finished.



          Using three lines (i = 5, while n != 1, and i += 2) to structure the loop — something that would be succinctly written in C as a for (i = 5; n != 1; i += 2) header — is un-Pythonic. Such counting loops are usually better written using some kind of range(), xrange(), enumerate(), or something from itertools. Here, itertools.chain() and itertools.count() would be appropriate.



          Without changing the spirit of your algorithm, I would write:



          import itertools

          def prime_factors(n):
          for i in itertools.chain([2], itertools.count(3, 2)):
          if n <= 1:
          break
          while n % i == 0:
          n //= i
          yield i


          is_prime()



          As mentioned above, you don't need is_prime() at all, if your only goal is to implement prime_factors().



          However, if you wanted to implement is_prime() anyway, you could tighten it up a bit. My main recommendation would be to avoid performing the i * i multiplication with each iteration. You would probably be better off computing the $sqrt{n}$ limit just once.



          Then, as with the other function, you should express the loop more Pythonically using range() or xrange(). Actually, you wouldn't need an explicit loop; you could use any() instead.



          So, if we stick to your algorithm in spirit, we could tighten up the implementation like this:



          def is_prime(n):
          if n < 3 or n % 2 == 0:
          return n == 2
          else:
          return not any(n % i == 0 for i in range(3, int(n**0.5 + 2), 2))





          share|improve this answer











          $endgroup$













          • $begingroup$
            using is_prime was really dumb. Good Observation.
            $endgroup$
            – user2305
            Mar 4 '16 at 10:51










          • $begingroup$
            @200_success @user2305 "If all factors smaller than i have been removed from n already, then i could not possibly be composite." i can and will be composite (it's just going through odd numbers, and most of them are composite). It's just that, if i is composite, it will not divide the remaining n, and I think that's what the OP was trying to skip. However, I do agree with removing the call to is_prime(): trying to avoid a O(1) operation with a O(log(n)) check is not exactly an optimization! :)
            $endgroup$
            – OxTaz
            Mar 4 '16 at 17:16












          • $begingroup$
            @200_success: you can break the loop if n < i * i and yield n as the largest prime factor.
            $endgroup$
            – Daniel
            Mar 6 '16 at 15:37














          6












          6








          6





          $begingroup$

          prime_factors()



          The single greatest improvement to performance that you could make would be to remove the call to is_prime() altogether. If all factors smaller than i have been removed from n already, then i could not possibly be composite.



          The next improvement you could make would be to turn prime_factors() into a generator. The function would no longer need to resize and recopy prime_factor_list whenever the list needs to grow beyond its estimated size. Furthermore, the caller could start making use of initial results before the entire factorization is finished.



          Using three lines (i = 5, while n != 1, and i += 2) to structure the loop — something that would be succinctly written in C as a for (i = 5; n != 1; i += 2) header — is un-Pythonic. Such counting loops are usually better written using some kind of range(), xrange(), enumerate(), or something from itertools. Here, itertools.chain() and itertools.count() would be appropriate.



          Without changing the spirit of your algorithm, I would write:



          import itertools

          def prime_factors(n):
          for i in itertools.chain([2], itertools.count(3, 2)):
          if n <= 1:
          break
          while n % i == 0:
          n //= i
          yield i


          is_prime()



          As mentioned above, you don't need is_prime() at all, if your only goal is to implement prime_factors().



          However, if you wanted to implement is_prime() anyway, you could tighten it up a bit. My main recommendation would be to avoid performing the i * i multiplication with each iteration. You would probably be better off computing the $sqrt{n}$ limit just once.



          Then, as with the other function, you should express the loop more Pythonically using range() or xrange(). Actually, you wouldn't need an explicit loop; you could use any() instead.



          So, if we stick to your algorithm in spirit, we could tighten up the implementation like this:



          def is_prime(n):
          if n < 3 or n % 2 == 0:
          return n == 2
          else:
          return not any(n % i == 0 for i in range(3, int(n**0.5 + 2), 2))





          share|improve this answer











          $endgroup$



          prime_factors()



          The single greatest improvement to performance that you could make would be to remove the call to is_prime() altogether. If all factors smaller than i have been removed from n already, then i could not possibly be composite.



          The next improvement you could make would be to turn prime_factors() into a generator. The function would no longer need to resize and recopy prime_factor_list whenever the list needs to grow beyond its estimated size. Furthermore, the caller could start making use of initial results before the entire factorization is finished.



          Using three lines (i = 5, while n != 1, and i += 2) to structure the loop — something that would be succinctly written in C as a for (i = 5; n != 1; i += 2) header — is un-Pythonic. Such counting loops are usually better written using some kind of range(), xrange(), enumerate(), or something from itertools. Here, itertools.chain() and itertools.count() would be appropriate.



          Without changing the spirit of your algorithm, I would write:



          import itertools

          def prime_factors(n):
          for i in itertools.chain([2], itertools.count(3, 2)):
          if n <= 1:
          break
          while n % i == 0:
          n //= i
          yield i


          is_prime()



          As mentioned above, you don't need is_prime() at all, if your only goal is to implement prime_factors().



          However, if you wanted to implement is_prime() anyway, you could tighten it up a bit. My main recommendation would be to avoid performing the i * i multiplication with each iteration. You would probably be better off computing the $sqrt{n}$ limit just once.



          Then, as with the other function, you should express the loop more Pythonically using range() or xrange(). Actually, you wouldn't need an explicit loop; you could use any() instead.



          So, if we stick to your algorithm in spirit, we could tighten up the implementation like this:



          def is_prime(n):
          if n < 3 or n % 2 == 0:
          return n == 2
          else:
          return not any(n % i == 0 for i in range(3, int(n**0.5 + 2), 2))






          share|improve this answer














          share|improve this answer



          share|improve this answer








          edited Mar 4 '16 at 9:13

























          answered Mar 4 '16 at 9:00









          200_success200_success

          130k16153417




          130k16153417












          • $begingroup$
            using is_prime was really dumb. Good Observation.
            $endgroup$
            – user2305
            Mar 4 '16 at 10:51










          • $begingroup$
            @200_success @user2305 "If all factors smaller than i have been removed from n already, then i could not possibly be composite." i can and will be composite (it's just going through odd numbers, and most of them are composite). It's just that, if i is composite, it will not divide the remaining n, and I think that's what the OP was trying to skip. However, I do agree with removing the call to is_prime(): trying to avoid a O(1) operation with a O(log(n)) check is not exactly an optimization! :)
            $endgroup$
            – OxTaz
            Mar 4 '16 at 17:16












          • $begingroup$
            @200_success: you can break the loop if n < i * i and yield n as the largest prime factor.
            $endgroup$
            – Daniel
            Mar 6 '16 at 15:37


















          • $begingroup$
            using is_prime was really dumb. Good Observation.
            $endgroup$
            – user2305
            Mar 4 '16 at 10:51










          • $begingroup$
            @200_success @user2305 "If all factors smaller than i have been removed from n already, then i could not possibly be composite." i can and will be composite (it's just going through odd numbers, and most of them are composite). It's just that, if i is composite, it will not divide the remaining n, and I think that's what the OP was trying to skip. However, I do agree with removing the call to is_prime(): trying to avoid a O(1) operation with a O(log(n)) check is not exactly an optimization! :)
            $endgroup$
            – OxTaz
            Mar 4 '16 at 17:16












          • $begingroup$
            @200_success: you can break the loop if n < i * i and yield n as the largest prime factor.
            $endgroup$
            – Daniel
            Mar 6 '16 at 15:37
















          $begingroup$
          using is_prime was really dumb. Good Observation.
          $endgroup$
          – user2305
          Mar 4 '16 at 10:51




          $begingroup$
          using is_prime was really dumb. Good Observation.
          $endgroup$
          – user2305
          Mar 4 '16 at 10:51












          $begingroup$
          @200_success @user2305 "If all factors smaller than i have been removed from n already, then i could not possibly be composite." i can and will be composite (it's just going through odd numbers, and most of them are composite). It's just that, if i is composite, it will not divide the remaining n, and I think that's what the OP was trying to skip. However, I do agree with removing the call to is_prime(): trying to avoid a O(1) operation with a O(log(n)) check is not exactly an optimization! :)
          $endgroup$
          – OxTaz
          Mar 4 '16 at 17:16






          $begingroup$
          @200_success @user2305 "If all factors smaller than i have been removed from n already, then i could not possibly be composite." i can and will be composite (it's just going through odd numbers, and most of them are composite). It's just that, if i is composite, it will not divide the remaining n, and I think that's what the OP was trying to skip. However, I do agree with removing the call to is_prime(): trying to avoid a O(1) operation with a O(log(n)) check is not exactly an optimization! :)
          $endgroup$
          – OxTaz
          Mar 4 '16 at 17:16














          $begingroup$
          @200_success: you can break the loop if n < i * i and yield n as the largest prime factor.
          $endgroup$
          – Daniel
          Mar 6 '16 at 15:37




          $begingroup$
          @200_success: you can break the loop if n < i * i and yield n as the largest prime factor.
          $endgroup$
          – Daniel
          Mar 6 '16 at 15:37













          4












          $begingroup$

          Your code is written fairly well, yet in is_prime you forgot to check whether the input integer is 2; just add this:



          if n == 2:
          return True


          Also, for some negative integers is_prime returns True. I suggest you add the following statement to prune them away:



          if n <= 1:
          return False





          share|improve this answer











          $endgroup$


















            4












            $begingroup$

            Your code is written fairly well, yet in is_prime you forgot to check whether the input integer is 2; just add this:



            if n == 2:
            return True


            Also, for some negative integers is_prime returns True. I suggest you add the following statement to prune them away:



            if n <= 1:
            return False





            share|improve this answer











            $endgroup$
















              4












              4








              4





              $begingroup$

              Your code is written fairly well, yet in is_prime you forgot to check whether the input integer is 2; just add this:



              if n == 2:
              return True


              Also, for some negative integers is_prime returns True. I suggest you add the following statement to prune them away:



              if n <= 1:
              return False





              share|improve this answer











              $endgroup$



              Your code is written fairly well, yet in is_prime you forgot to check whether the input integer is 2; just add this:



              if n == 2:
              return True


              Also, for some negative integers is_prime returns True. I suggest you add the following statement to prune them away:



              if n <= 1:
              return False






              share|improve this answer














              share|improve this answer



              share|improve this answer








              edited Mar 4 '16 at 8:46

























              answered Mar 4 '16 at 6:44









              coderoddecoderodde

              15.9k638127




              15.9k638127























                  3












                  $begingroup$

                  prime_factors never calls is_prime with a number that's divisible by 2 or 3. is_prime could be faster if it used this knowledge. However, if is_prime will use this knowledge, then it may be a bit misleading in global scope. So you could move the definition of is_prime inside of prime_factors.



                  Although the code is Pythonic alright, it would be more idiomatic to use a prime generator to get the next prime factor, instead of iterating from 5 upwards. Given a prime generator gen, the final loop of the code would become:



                  while n != 1:
                  prime = next(gen)
                  while not n % prime:
                  prime_factor_list.append(prime)
                  n //= prime





                  share|improve this answer









                  $endgroup$


















                    3












                    $begingroup$

                    prime_factors never calls is_prime with a number that's divisible by 2 or 3. is_prime could be faster if it used this knowledge. However, if is_prime will use this knowledge, then it may be a bit misleading in global scope. So you could move the definition of is_prime inside of prime_factors.



                    Although the code is Pythonic alright, it would be more idiomatic to use a prime generator to get the next prime factor, instead of iterating from 5 upwards. Given a prime generator gen, the final loop of the code would become:



                    while n != 1:
                    prime = next(gen)
                    while not n % prime:
                    prime_factor_list.append(prime)
                    n //= prime





                    share|improve this answer









                    $endgroup$
















                      3












                      3








                      3





                      $begingroup$

                      prime_factors never calls is_prime with a number that's divisible by 2 or 3. is_prime could be faster if it used this knowledge. However, if is_prime will use this knowledge, then it may be a bit misleading in global scope. So you could move the definition of is_prime inside of prime_factors.



                      Although the code is Pythonic alright, it would be more idiomatic to use a prime generator to get the next prime factor, instead of iterating from 5 upwards. Given a prime generator gen, the final loop of the code would become:



                      while n != 1:
                      prime = next(gen)
                      while not n % prime:
                      prime_factor_list.append(prime)
                      n //= prime





                      share|improve this answer









                      $endgroup$



                      prime_factors never calls is_prime with a number that's divisible by 2 or 3. is_prime could be faster if it used this knowledge. However, if is_prime will use this knowledge, then it may be a bit misleading in global scope. So you could move the definition of is_prime inside of prime_factors.



                      Although the code is Pythonic alright, it would be more idiomatic to use a prime generator to get the next prime factor, instead of iterating from 5 upwards. Given a prime generator gen, the final loop of the code would become:



                      while n != 1:
                      prime = next(gen)
                      while not n % prime:
                      prime_factor_list.append(prime)
                      n //= prime






                      share|improve this answer












                      share|improve this answer



                      share|improve this answer










                      answered Mar 4 '16 at 7:40









                      janosjanos

                      98.1k12125350




                      98.1k12125350























                          0












                          $begingroup$

                          Few additional thoughts to Fast Number Factorization in Python answer.



                          is_prime()



                          In case if you have multiple consequent calls you should use something like Sieve_of_Eratosthenes. If you will, time to generate sieve will depend on maximum value of number to factorize but total time will be reduces.



                          prime_factors()



                          There is one thing you miss in your code. Lets take prime number, let is be
                          $ 10007 $ and multiply it by $ 2 $, we will receive $ 20014 $. Its factorization will be $ 20014 = 10007 times 2 $.



                          Now lets analyze your prime_factors. You will find that $ 2 $ is prime divisor of $ 20014 $ and will continue to iterate through all prime numbers up to $ 10007 $ but actually you have to iterate up to square root of initial number, because if you cross this line and reminder still not equal $ 1 $ than it is prime.



                          This trick can reduce time for such cases.



                          As the result, you can assume that you need to generate sieve up to square root of highest number.






                          share|improve this answer











                          $endgroup$


















                            0












                            $begingroup$

                            Few additional thoughts to Fast Number Factorization in Python answer.



                            is_prime()



                            In case if you have multiple consequent calls you should use something like Sieve_of_Eratosthenes. If you will, time to generate sieve will depend on maximum value of number to factorize but total time will be reduces.



                            prime_factors()



                            There is one thing you miss in your code. Lets take prime number, let is be
                            $ 10007 $ and multiply it by $ 2 $, we will receive $ 20014 $. Its factorization will be $ 20014 = 10007 times 2 $.



                            Now lets analyze your prime_factors. You will find that $ 2 $ is prime divisor of $ 20014 $ and will continue to iterate through all prime numbers up to $ 10007 $ but actually you have to iterate up to square root of initial number, because if you cross this line and reminder still not equal $ 1 $ than it is prime.



                            This trick can reduce time for such cases.



                            As the result, you can assume that you need to generate sieve up to square root of highest number.






                            share|improve this answer











                            $endgroup$
















                              0












                              0








                              0





                              $begingroup$

                              Few additional thoughts to Fast Number Factorization in Python answer.



                              is_prime()



                              In case if you have multiple consequent calls you should use something like Sieve_of_Eratosthenes. If you will, time to generate sieve will depend on maximum value of number to factorize but total time will be reduces.



                              prime_factors()



                              There is one thing you miss in your code. Lets take prime number, let is be
                              $ 10007 $ and multiply it by $ 2 $, we will receive $ 20014 $. Its factorization will be $ 20014 = 10007 times 2 $.



                              Now lets analyze your prime_factors. You will find that $ 2 $ is prime divisor of $ 20014 $ and will continue to iterate through all prime numbers up to $ 10007 $ but actually you have to iterate up to square root of initial number, because if you cross this line and reminder still not equal $ 1 $ than it is prime.



                              This trick can reduce time for such cases.



                              As the result, you can assume that you need to generate sieve up to square root of highest number.






                              share|improve this answer











                              $endgroup$



                              Few additional thoughts to Fast Number Factorization in Python answer.



                              is_prime()



                              In case if you have multiple consequent calls you should use something like Sieve_of_Eratosthenes. If you will, time to generate sieve will depend on maximum value of number to factorize but total time will be reduces.



                              prime_factors()



                              There is one thing you miss in your code. Lets take prime number, let is be
                              $ 10007 $ and multiply it by $ 2 $, we will receive $ 20014 $. Its factorization will be $ 20014 = 10007 times 2 $.



                              Now lets analyze your prime_factors. You will find that $ 2 $ is prime divisor of $ 20014 $ and will continue to iterate through all prime numbers up to $ 10007 $ but actually you have to iterate up to square root of initial number, because if you cross this line and reminder still not equal $ 1 $ than it is prime.



                              This trick can reduce time for such cases.



                              As the result, you can assume that you need to generate sieve up to square root of highest number.







                              share|improve this answer














                              share|improve this answer



                              share|improve this answer








                              edited Apr 13 '17 at 12:40









                              Community

                              1




                              1










                              answered Mar 4 '16 at 9:57









                              outoftimeoutoftime

                              1,392517




                              1,392517























                                  0












                                  $begingroup$

                                  def print_factors(x):enter code here
                                  print("The factors of",x,"are:")enter code here
                                  for i in range(1, num+1):enter code here
                                  print()enter code here
                                  print(i,"#--->",end=' ')enter code here
                                  for j in range(1,i+1):enter code here
                                  if i % j == 0:enter code here
                                  print(j,end=', ')enter code here
                                  num = int(input("Enter a limit of the natural sequenced numbers: "))enter code here
                                  print_factors(num)enter code here






                                  share|improve this answer








                                  New contributor




                                  Vasanth is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                  Check out our Code of Conduct.






                                  $endgroup$


















                                    0












                                    $begingroup$

                                    def print_factors(x):enter code here
                                    print("The factors of",x,"are:")enter code here
                                    for i in range(1, num+1):enter code here
                                    print()enter code here
                                    print(i,"#--->",end=' ')enter code here
                                    for j in range(1,i+1):enter code here
                                    if i % j == 0:enter code here
                                    print(j,end=', ')enter code here
                                    num = int(input("Enter a limit of the natural sequenced numbers: "))enter code here
                                    print_factors(num)enter code here






                                    share|improve this answer








                                    New contributor




                                    Vasanth is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                    Check out our Code of Conduct.






                                    $endgroup$
















                                      0












                                      0








                                      0





                                      $begingroup$

                                      def print_factors(x):enter code here
                                      print("The factors of",x,"are:")enter code here
                                      for i in range(1, num+1):enter code here
                                      print()enter code here
                                      print(i,"#--->",end=' ')enter code here
                                      for j in range(1,i+1):enter code here
                                      if i % j == 0:enter code here
                                      print(j,end=', ')enter code here
                                      num = int(input("Enter a limit of the natural sequenced numbers: "))enter code here
                                      print_factors(num)enter code here






                                      share|improve this answer








                                      New contributor




                                      Vasanth is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                      Check out our Code of Conduct.






                                      $endgroup$



                                      def print_factors(x):enter code here
                                      print("The factors of",x,"are:")enter code here
                                      for i in range(1, num+1):enter code here
                                      print()enter code here
                                      print(i,"#--->",end=' ')enter code here
                                      for j in range(1,i+1):enter code here
                                      if i % j == 0:enter code here
                                      print(j,end=', ')enter code here
                                      num = int(input("Enter a limit of the natural sequenced numbers: "))enter code here
                                      print_factors(num)enter code here







                                      share|improve this answer








                                      New contributor




                                      Vasanth is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                      Check out our Code of Conduct.









                                      share|improve this answer



                                      share|improve this answer






                                      New contributor




                                      Vasanth is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                      Check out our Code of Conduct.









                                      answered 22 mins ago









                                      VasanthVasanth

                                      1




                                      1




                                      New contributor




                                      Vasanth is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                      Check out our Code of Conduct.





                                      New contributor





                                      Vasanth is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                      Check out our Code of Conduct.






                                      Vasanth is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                                      Check out our Code of Conduct.






























                                          draft saved

                                          draft discarded




















































                                          Thanks for contributing an answer to Code Review Stack Exchange!


                                          • Please be sure to answer the question. Provide details and share your research!

                                          But avoid



                                          • Asking for help, clarification, or responding to other answers.

                                          • Making statements based on opinion; back them up with references or personal experience.


                                          Use MathJax to format equations. MathJax reference.


                                          To learn more, see our tips on writing great answers.




                                          draft saved


                                          draft discarded














                                          StackExchange.ready(
                                          function () {
                                          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f121862%2ffast-number-factorization-in-python%23new-answer', 'question_page');
                                          }
                                          );

                                          Post as a guest















                                          Required, but never shown





















































                                          Required, but never shown














                                          Required, but never shown












                                          Required, but never shown







                                          Required, but never shown

































                                          Required, but never shown














                                          Required, but never shown












                                          Required, but never shown







                                          Required, but never shown







                                          Popular posts from this blog

                                          How to make a Squid Proxy server?

                                          Is this a new Fibonacci Identity?

                                          Touch on Surface Book