Python Finding Prime Factors

Python Finding Prime Factors

This question was the first link that popped up when I googled python prime factorization.
As pointed out by @quangpn88, this algorithm is wrong (!) for perfect squares such as n = 4, 9, 16, ... However, @quangpn88s fix does not work either, since it will yield incorrect results if the largest prime factor occurs 3 or more times, e.g., n = 2*2*2 = 8 or n = 2*3*3*3 = 54.

I believe a correct, brute-force algorithm in Python is:

def largest_prime_factor(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
    return n

Dont use this in performance code, but its OK for quick tests with moderately large numbers:

In [1]: %timeit largest_prime_factor(600851475143)
1000 loops, best of 3: 388 ┬Ás per loop

If the complete prime factorization is sought, this is the brute-force algorithm:

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

Ok. So you said you understand the basics, but youre not sure EXACTLY how it works. First of all, this is a great answer to the Project Euler question it stems from. Ive done a lot of research into this problem and this is by far the simplest response.

For the purpose of explanation, Ill let n = 20. To run the real Project Euler problem, let n = 600851475143.

n = 20 
i = 2

while i * i < n:
    while n%i == 0:
        n = n / i
    i = i + 1

print (n)

This explanation uses two while loops. The biggest thing to remember about while loops is that they run until they are no longer true.

The outer loop states that while i * i isnt greater than n (because the largest prime factor will never be larger than the square root of n), add 1 to i after the inner loop runs.

The inner loop states that while i divides evenly into n, replace n with n divided by i. This loop runs continuously until it is no longer true. For n=20 and i=2, n is replaced by 10, then again by 5. Because 2 doesnt evenly divide into 5, the loop stops with n=5 and the outer loop finishes, producing i+1=3.

Finally, because 3 squared is greater than 5, the outer loop is no longer true and prints the result of n.

Thanks for posting this. I looked at the code forever before realizing how exactly it worked. Hopefully, this is what youre looking for in a response. If not, let me know and I can explain further.

Python Finding Prime Factors

It looks like people are doing the Project Euler thing where you code the solution yourself. For everyone else who wants to get work done, theres the primefac module which does very large numbers very quickly:

#!python

import primefac
import sys

n = int( sys.argv[1] )
factors = list( primefac.primefac(n) )
print n.join(map(str, factors))

Leave a Reply

Your email address will not be published.