CODEWITHSUNDEEP
python-3.xfor-loopprime-factoring
Curious-Bee
Curious-Bee

Reputation: 19

Finding prime factors of a number using "for loop" in python

I know how to implement this using a while-loop, but I need to figure out a solution using a for-loop. For a given num = 56 my code below outputs [2, 7, 4], whereas the right answer would be [2,2,2,7]. where am I going wrong?

def prime_fac(num):
    a = num
    pf = []
    for x in range(2,a):
        if a % x == 0:
            if x == 2 or x == 3:
                pf.append(x)
                a = a//x
            else:
                for y in range(2,x):
                    if (x % y) == 0:
                        break
                else:
                    pf.append(x)
                    a = a // x
        else:
            continue
    if a>1:
        pf.append(a)
    print (f"Prime factors of {num} are {pf}")
number = int(input('Enter a number to find its prime factors: '))
prime_fac(number)

Upvotes: 1

Views: 2950

Answers (1)

Mr. T
Mr. T

Reputation: 12410

Your problem is the algorithm, not so much the Python code. Your program increases the divisor x, when it divides a, without checking, if x**i (i>1) divides a. In your output, the last number represent a product of all prime numbers that are more than once a divisor of a. You could employ debuggers like PythonTutor to find out, where your program does not, what you expect.

Actually, I just wanted to give you the pseudocode to improve your algorithm, so you could implement the algorithm. But then I noticed, that the pseudocode was pretty much the same in Python:

def prime_fac(num):
    a = num
    pf = []
    #ranges in Python don't include the last element, therefore we need a + 1 to detect also prime numbers
    for x in range(2, a + 1):
        #check if x is divisor and repeat
        while a % x == 0:
            pf.append(x)
            a = a // x

        #all factors found?
        if a == 1:
            #yes, return list with prime factors
            return pf 
        #no, go to next x

And now, you can try to improve the efficiency of your algorithm because this strategy is rather slow.

Upvotes: 1

Related Questions