CODEWITHSUNDEEP
pythonloopsrecursion
Logan Nguyen
Logan Nguyen

Reputation: 31

Prime factors of a number in Python

I have a task to generate the prime factors of a number

I input 396, I expect 2*2*3*3*11 back.

I came up with an idea of recursion on a function that takes 2 arguments: the number and the result as a list.

I expect the steps to be like this:

(396, [empty])
(198,[2])
(99,[2,2])
(33, [2,2,3])
(11, [2,2,3,3])
(1, [2,2,3,3,11])

There we go, when the number reachs 1, it means the job is done, we take the list as a result.

Here is my code in Python:

import math

def list_of_prime(x):
    filtered_list = list(range(2, x))
    for i in range (2, int(round(math.sqrt(x), 0))):
        filtered_list = list(filter(lambda x: x == i or x % i, filtered_list))
    return filtered_list

def prime_factor(x,y):
    if (x-1) != 0:
        for i in list_of_prime(x):
            if x % i == 0:
                y.append(i)
                x = x // i
                print(x, y)
                prime_factor(x, y)
        return y

prime_factor(396,[])

The result is

198 [2]
99 [2, 2]
33 [2, 2, 3]
11 [2, 2, 3, 3]
1 [2, 2, 3, 3, 11]
3 [2, 2, 3, 3, 11, 11]
33 [2, 2, 3, 3, 11, 11, 3]
11 [2, 2, 3, 3, 11, 11, 3, 3]
1 [2, 2, 3, 3, 11, 11, 3, 3, 11]
3 [2, 2, 3, 3, 11, 11, 3, 3, 11, 11]
66 [2, 2, 3, 3, 11, 11, 3, 3, 11, 11, 3]
33 [2, 2, 3, 3, 11, 11, 3, 3, 11, 11, 3, 2]
11 [2, 2, 3, 3, 11, 11, 3, 3, 11, 11, 3, 2, 3]
1 [2, 2, 3, 3, 11, 11, 3, 3, 11, 11, 3, 2, 3, 11]
11 [2, 2, 3, 3, 11, 11, 3, 3, 11, 11, 3, 2, 3, 11, 3]
1 [2, 2, 3, 3, 11, 11, 3, 3, 11, 11, 3, 2, 3, 11, 3, 11]
6 [2, 2, 3, 3, 11, 11, 3, 3, 11, 11, 3, 2, 3, 11, 3, 11, 11]
3 [2, 2, 3, 3, 11, 11, 3, 3, 11, 11, 3, 2, 3, 11, 3, 11, 11, 2]
1 [2, 2, 3, 3, 11, 11, 3, 3, 11, 11, 3, 2, 3, 11, 3, 11, 11, 2, 3]

It looks like working, but when x is 1, somehow x still pass the condition check, and the iterator 'i' actually goes from 2 to 11 after the first if, x & i means 1 % 11 can't be 0, but it still got past the second inner if then got added to the list by "y.append(i)" line; hence I see the double '11' in the list. I have no idea how the rest of the result is generated.

I ran visual studio code on Windows with Linux for windows enabled, I installed python through bash for windows terminal.

Upvotes: 1

Views: 266

Answers (1)

Jean-François Fabre
Jean-François Fabre

Reputation: 140178

when you call your function recursively in your loop:

if x % i == 0:
    y.append(i)
    x = x // i
    print(x, y)
    prime_factor(x, y)

you're not returning the result. So it keeps looping, appending unwanted/dupe values with y.append(i) and returns y in the end.

It's a variation of the classic Why does my function return None?, except that here, the function doesn't return None because it returns y as a fallback.

By doing:

return prime_factor(x, y)

I get

198 [2]
99 [2, 2]
33 [2, 2, 3]
11 [2, 2, 3, 3]

It's missing the line with 1 (which is difficult to achieve without post-processing & only print statements) but it's very close to what you're asking.

Aside:

  • don't generate the prime list at each iteration. Generate once and use it in all calls
  • use a Sieve of Erathostenes algorithm, which is way more efficient (the formula you're applying is more a demo of how lambda & filter work for classic problems)

Upvotes: 1

Related Questions