0

I have been trying to solve Problem #3 in ProjectEuler in python. I have tried using recursion to get factors of my factors. But I keep on running into a recursive limit reached error for some reason. Can anyone help me out as to why its happening?

def getPrimeFactors(y):
  AllFactors = [[x, int(y/x)] for x in range(1, (int(math.sqrt(y)+1))) if y%x==0]
  Flattened_AF = [j for i in AllFactors for j in i]
  print(AllFactors)
  print(Flattened_AF)

  if len(Flattened_AF)==2:
    print(Flattened_AF)
    return Flattened_AF
  else:
    PrimeFactors = [x for x in Flattened_AF if len(getPrimeFactors(x))==2]
    print (f'loop in else - {PrimeFactors}')
    print(max(PrimeFactors)

getPrimeFactors(4)

This is the problem as quoted in the website.

I am sorry if the code readability quality is a bit low but I had been trying to debug for a long time in vain.

Rhythorn
  • 13
  • 2
  • in `[x, int(y/x)] for x in range(1, (int(math.sqrt(y)+1))) if y%x==0`, the first, smallest `x` that passes the test is guaranteed to be prime. no need to test it. then, no need to find all prime factors, just the biggest one. for that, keeping the *biggest-known-so-far* is enough. you think you get the `int(y/x)` for free, but that's false economy here, as it's not guaranteed to be prime, and its prime factors are not guaranteed to be the biggest of the original. lastly, why recursion, in Python? why not loop? – Will Ness May 22 '20 at 14:52
  • I've done this problem on Project Euler before. You're going to find that using recursion or a for loop will work, but it will take a long time for the computer to calculate the answer. (If I remember correctly, I think it took me about an hour to calculate this answer using a for loop, and it'll take even longer if you use recursion). There is a formula that solves this problem in a super efficient way, but it's nothing you could ever come up with on your own. You either know it or you don't. It's called the Sieve of Eratosthenes. – hostingutilities.com May 22 '20 at 14:58
  • @WillNess The initial idea was that I would identify all the factors of a certain number until its square root because after that it will repeat its factor pair (y/x) so as to increase code efficiency for big numbers. Then I would check the the length of each original factor's factor list to see whether or not it was prime (will have length of 2). Hence the initialization to 1. As for recursion, I can see now after a bit more debugging that it just digs itself into a hole and inherently wont work so I have decided to define another function to check for primes. – Rhythorn May 22 '20 at 16:25
  • @wp-overwatch.com yea.. I initially had tried the using a for loop with a simple brute force but that wouldn't have worked as you said so I tried another way that I described in my above reply which involves setting the square root as the upper limit as mentioned here. [link](https://stackoverflow.com/questions/6800193/what-is-the-most-efficient-way-of-finding-all-the-factors-of-a-number-in-python). I'll be sure to check out the Sieve of Eratosthenes too. – Rhythorn May 22 '20 at 16:29
  • @Rhythorn with the proper algorithm you won't need to check for primality. re-read my comment. :) one more hint: when you find the smallest factor (which is automatically prime) you can use it to make the original number into another, smaller one, with which you could find all the remaining prime factors. then proceed with this new, smaller number and repeat the process. stopping at the `sqrt` is a very good idea, continue using it. you don't need the sieve here. – Will Ness May 22 '20 at 17:59
  • 1
    @WillNess Got it! I cant believe the prime factorization didn't hit me earlier enough. With that and the square root rule, finding the factors for a number as big as a septillion takes less than a minute. Thanks for the push! – Rhythorn May 23 '20 at 07:11

1 Answers1

0

When you define AllFactors for in input y, you iterate from 1, so the same number y is always contained within AllFactors. As such, when you call getPrimeFactors on the input, that same input y is passed, so this becomes an infinite loop.

Iterating from 2 instead of 1 stops the recursion error.

Also, just a tip, typically in python variables names begin with a lower case and classes begin with uppercase. There is more about naming conventions here:https://visualgit.readthedocs.io/en/latest/pages/naming_convention.html.

Alex Edwards
  • 18
  • 2
  • Iterating from two did stop the recursion errors and also showed me the fault in the logic my approach had to solve this problem. It ends up with an empty set by digging through the factors unnecessarily. I decided to use an external function instead of a recursion to check for primes. Thank you for the answer and tip! – Rhythorn May 22 '20 at 16:34
  • No worries, in that case you can mark this answer as correct! Good luck. – Alex Edwards May 24 '20 at 08:32