Python Prime Factors

Question

Again im stuck on a problem.. I wanted to create a function that puts out all prim factors of a given number. It was pretty much finished but it wouldnt put out correct factors for numbers which have the same prim factor more than once, for example: 20 - 5, 2, 2 So i added a while loop which checked if the product of all factors equals the number i put in. Thanks for any help :)

prime_numbers = []

def prime_gen(upper_limit):
    for i in range(2, upper_limit):
        for j in range(2, i):
            if i % j == 0:
                break
        else:
            prime_numbers.append(i)
    return prime_numbers



def list_product(list):
    sum = 1
    for i in list:
        sum *= i
    return sum




prime_factors = []
def prime_factor(number):
    while list_product(prime_factors) != number:    #without the while it checked every factor only once
        for i in reversed(prime_gen(number)):
            while number % i != 0:
                break
            else:
                if i != 1:
                    number /= i
                    prime_factors.append(i)
                    continue
                else:
                    break

prime_factor(20)
print (prime_factors)

It's unclear what you are asking here. Does your code not do what you expect? What is it doing? What do you expect it to do? — Greg Hewgill, May 10 '15 at 09:51
I want it to check a number on all its prime factors and it gives me the error: float cannot be interpreted as int — antoni, May 10 '15 at 09:57
possible duplicate of [Prime factorization - list](http://stackoverflow.com/questions/16996217/prime-factorization-list) — dting, May 10 '15 at 10:51

Padraic Cunningham · Answer 1 · 2015-05-10T11:00:20.340

Just use a for loop, getting you list of primes from prime_gen:

def prime_gen(upper_limit):
    prime_numbers = [2]
    for i in range(3, upper_limit,2):
        for j in range(2, i):
            if i % j == 0:
                break
        else:
            prime_numbers.append(i)
    return prime_numbers


def prime_factors(n):
    p_f = []
    for prime in prime_gen(n):
        # while n is divisible keep adding the prime
        while n % prime == 0:
            p_f.append(prime)
            # update n by dividing  by the prime
            n //= prime
    if n > 1:
        p_f.append(n)
    return p_f

print(prime_factors(40))
[2, 2, 2, 5] # ->  2*2*2*5

If you take 40 as an example:

(40, 2) # first prime 2, 40 is divisible by 2
(20, 2) # 40 //= 2 == 20, 20 is divisible by 2
(10, 2) # 20 //= 2 == 10, 10 is divisible by 2
(5, 5)  # 10 //=2 == 5, 5  is not evenly divisible by 2 or 3 so we get 5

If you want a fast way to generate the primes, you can use a sieve:

 from math import sqrt

def sieve_of_eratosthenes(n):
    primes = range(3, n + 1, 2) # primes above 2 must be odd so start at three and increase by 2
    for base in xrange(len(primes)):
        if primes[base] is None:
           continue
        if primes[base] >= sqrt(n): # stop at sqrt of n
            break
        for i in xrange(base + (base + 1) * primes[base], len(primes), primes[base]):
            primes[i] = None
    primes.insert(0,2)
    sieve=filter(None, primes)
    return  sieve

score 0 · Answer 2 · answered May 10 '15 at 10:01

0

The error you are getting (TypeError: 'float' object cannot be interpreted as an integer) is ultimately caused by this statement:

                number /= i

In Python 3, the result of /= is always a float. To perform integer division (so that number remains an integer), use:

                number //= i

After fixing this, you'll find that you have a logic error that causes an infinite loop.

answered May 10 '15 at 10:01

Greg Hewgill

951,095
183
1,149
1,285

Thanks a lot :) But could you explain why it doesnt stop when it has found all the factors - before i added the while loop it worked completely fine expect that every factor could appear only once. – antoni May 10 '15 at 10:14

Python Prime Factors

2 Answers2