Python code stucks in Iterating although it found the solution

Question

I'm trying to write a python code to find the prime factors of any given number

def pf(n):
    for i in range(2,n):
        if n%i==0: #find the factors
            for j in range(2,i): #check if the factor is prime
                if i%j==0:
                    break
            else: #find the prime ones
                print(i)

My problem is that this code works fine with small numbers however with big numbers i have to interrupt the execution
for example:

pf(600851475143)
71
839
1471
6857
Traceback (most recent call last):
  File "<pyshell#11>", line 1, in <module>
    pf(600851475143)
  File "<pyshell#1>", line 2, in pf
    for i in range(2,n):
KeyboardInterrupt  

the prime factors of this big number were found in less than a second, so my question is how to tweak this code to stop unnecessary iterations after finding the factors with the use of the for not the while loop

Answer 1

You can speed things up by dividing n by the obtained value in each iteration step. This way you decrease the number you are iterating. I would implement something like this (not yet sure if this is optimal and results in the lowest number of operations):

from math import sqrt

def pf(n):
    if n == 1: 
        return
    if n % 2 == 0:
        print(2)
        pf(n/2)
        return
    for i in range(3, int(sqrt(n))+1, 2):
        if n % i == 0:
            for j in range(3, int(sqrt(i))+1, 2):
                if i % j == 0:
                    break
            else:
                print(i)
                pf(n/i)
                return
    print(n)

Note, if using the improvement of looping until the root of the number we omit the case that the number itself is a prime number. However, if the function does not result any prime factors it is save to assume that the input is a prime number itself.

The return statements stop the main loop (and the function) after the recursive call. So each call of the function only results in one value and a call for the function on the result of the division of the number by its found prime.

If you make a set with all the prime numbers and check if the value is in this set you will win some time, instead of looping over all values.

Compared to the non-recursive solution by jonrsharpe this one is almost four times as fast:

>>> print timeit.timeit("pf(600851475143)", setup="from __main__ import pf", number=1)
71
839
1471
6857
0.00985789299011
>>> print timeit.timeit("pf2(600851475143)", setup="from __main__ import pf2", number=1)
71
839
1471
6857
0.0450129508972

The implementation is limited by the overflow limit of range(), which results in an overflow for the input value (600851475143**2)+1. More details on the maximum size for range can be found in this question: Python: Range() maximum size; dynamic or static?

A possible issue with this solution could be that the maximum recursion depth is achieved. For more details on that visit this question: Maximum recursion depth

Answer 2

You could try adding prime factors to a list as you find them, and see if they multiply to make the number you are trying to factorize, but I think that might add more time than it would save.

As suggested in the comments, you could also stop at the square root of the number - using for i in range(2, sqrt(n) + 1):.

In terms of generally speeding it up you could also try creating a set of primes, and adding to it when you find them in the 5th line. Example:

if i in primes:
   print(i)
else:
    for j in range(2,i):   # check if the factor is prime
        if i%j==0:
            break

Answer 3

One further point - use xrange() rather than range(), so you do not internally create the list of all numbers to iterate: (if you are using Python 2 !)

What is the difference between range and xrange functions in Python 2.X?

Answer 4

just iterate square root of value, this is how you can iterate through less nombers and use generators to skip repeated iteration usinf for else

from math import sqrt
def pf(n):
    n = int(sqrt(n))
    for i in xrange(2, n): # in python2 use `range` for python3
        for j in xrange(2,i):
            if i%j == 0:
                break
        else:
            yield i # this will return when prime nomber will found.

print list(pf(4356750))

Answer 5

Here's how I would do it:

from math import sqrt

def pf(n):
    """Print the prime factors of n."""
    if n % 2 == 0:
        print(2)
    for i in range(3, int(sqrt(n))+1, 2):
        if n % i == 0: # i is a factor of n
            for j in range(3, int(sqrt(i))+1, 2):
                if i % j == 0:
                    break
            else: # i is also prime
                print(i)

By factoring out the checks for 2 you can almost halve the search space, and using the fact that all prime factors must be below the square root of a number you cut it down even further. This takes about a quarter of a second for 600851475143:

>>> import timeit
>>> timeit.timeit("pf(600851475143)", setup="from __main__ import pf", number=1)
71
839
1471
6857
0.27306951168483806

Another option would be to use a prime sieve to generate all primes below n, then filter out those that are also factors of n (effectively the reverse operation).