Compute prime factors in python

Question

I currently have a list containing numbers:

lst = [3,4,6]

and I'm trying to compute the prime factors of the numbers in the list where i obtain the output of

3^1
2^2
2^1 x 3^1

Here's what i tried:

def prime_factors(lst):
   for j in range(len(lst)):
       i = 2
       factors = []
       while i*i <= j:
           if j%i:
               i+=1
           else:
               j//= i
               factors.append(i)
       if j > 1:
           factors.append(j)
  return factors

but I'm getting [2] as the output. Would appreciate some help on this.

your `while i*i <= j:` condition is the problem. It exits when `i*i` is `<=` the value of of element on the list and your initial condition is `i=2` so for `4` , `i*i` matches the exit condition and hence the code does not go into the loop. Also you are not going to get prime factors with this code. as you do incremental increase of `i` and not go through a list of primes. — jkhadka, Oct 09 '18 at 08:50
Also, I think you want to use `for j in lst:` rather than `for j in range(len(lst)):` as at the moment, the values of lst aren't being accessed. You're iterating through from 0,1,2,... up to the length of the list. — Andrew McDowell, Oct 09 '18 at 08:55
http://codereview.stackexchange.com contains a ton of examples of _working_ code. Look at them. — Jean-François Fabre, Oct 09 '18 at 08:57
have a look at [primefac module](https://pypi.org/project/primefac/) and at this so [link](https://stackoverflow.com/questions/15347174/python-finding-prime-factors). — bipin_s, Oct 09 '18 at 09:03

Albin Paul · Answer 1 · 2018-10-09T09:16:36.010

Well i did it from scratch , It uses a modification of the prime number sieve algorithm .

from math import sqrt
from collections import Counter
def prime_factors(lst):
    maximumnumber=max(lst)
    primesieve=[0]*(maximumnumber+1)
    primesieve[0]=1
    primesieve[1]=1
    #DOING PRIME NUMBER SIEVE
    for i in range(2,int(sqrt(maximumnumber))+1):
        if(primesieve[i]==0):
            for j in range(2*i,len(primesieve),i):
                primesieve[j]=i

    for j in range(len(lst)):
        num=lst[j]
        factors=[]
        #take each number(num) and divided it by a prime number (primesieve[num])
        #do it until you find no more prime factors for number
        while(primesieve[num]>0):

            factors.append(primesieve[num])
            num=num//primesieve[num]
        factors.append(num)
        yield Counter(factors)

for i in prime_factors([3,4,6]):
    print(i)

Output

Counter({3: 1})
Counter({2: 2})
Counter({2: 1, 3: 1})

Ill explain what i have done

Found prime numbers between the 0 and maximum element in the list using the prime number sieve algorithm , Link to a the algorithm , I just modified one part that algorithm that is instead of using a the primenumber array as boolean i used ,Integer to show which number it was divided with
Iterate through the numbers and find all the prime factors

Compute prime factors in python

1 Answers1