Recursion Issue in a Prime Factorization + Optimization [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 9 years ago.

Improve this question

I am creating a module for the factors of any number. In it, I also have two functions (one that leads to a calling of the other) that find the prime factorization of the number, n.

The problem that comes up is a recursion error (if my definition of recursion is correct). When I call the function for a number, it prints all of the prime factors, then it adds the last two prime factors and prints it again, and does this repeatedly, to an apparent no end.

My code so far:

def primeFactors(n):
   from primenum2 import isPrime
   from math import sqrt
   global pFact, y
   x, pFact, y = 2, [], 0
   if isPrime(n):
      return n
   else:
      while x <= sqrt(n):
         if isPrime(x) and (n%x==0):
            pFact.append(x)
            y = n / x
            if isPrime(y):
               pFact.append(y)
               print pFact
               break
            else:
               primeFactors2(y)
         else:
            x += 1

#NEW FUNCTION - I made two functions to avoid another recursion error that was occuring.

def primeFactors2(y):
   from primenum2 import isPrime
   from math import sqrt
   z = 2
   while z <= sqrt(y):
      if isPrime(z) and (y%z==0):
         pFact.append(z)
         y = y / z
         if isPrime(y):
            pFact.append(y)
            print pFact
            break
         else:
            primeFactors2(y)
      else:
         z += 1

When I input (in the Shell): primeFactors(600851475143) <---This was for Project Euler originally

Expected Output (I already solved the problem): [71, 839, 1471, 6857L]

Actual Output:

[71, 839, 1471, 6857L]
[71, 839, 1471, 6857L, 1471, 6857L]
[71, 839, 1471, 6857L, 1471, 6857L, 71, 839, 1471, 6857L]
[71, 839, 1471, 6857L, 1471, 6857L, 71, 839, 1471, 6857L, 1471, 6857L]
[71, 839, 1471, 6857L, 1471, 6857L, 71, 839, 1471, 6857L, 1471, 6857L, 71, 839, 1471, 6857L]

It does this over and over, appending 1471 and 6857L to the list then printing it again. Then, it adds all of the prime factors again then prints it again. Not sure why it does this. Any input is greatly appreciated. Also, if there are any ways to make this code faster/ more Pythonic, please tell me :) Thanks

Answer 1

You're doing too much work. You don't need isPrime or recursive functions. Here is pseudocode for the simplest possible function for factoring integers, based on trial division:

define factors(n)
  f := 2
  while f * f <= n
    if n % f == 0
      output f
      n := n / f
    else
      f := f + 1
  output n

Though that is sufficient for Project Euler #3, there are better ways to factor integers. When you are ready, I modestly recommend this essay at my blog, which includes this factoring algorithm, and others, implemented in five languages including Python.