# Python Finding Prime Factors

Posted on

### Question :

Python Finding Prime Factors

Two part question:

1) Trying to determine the largest prime factor of 600851475143, I found this program online that seems to work. The problem is, I’m having a hard time figuring out how it works exactly, though I understand the basics of what the program is doing. Also, I’d like if you could shed some light on any method you may know of finding prime factors, perhaps without testing every number, and how your method works.

Here’s the code that I found online for prime factorization [NOTE: This code is incorrect. See Stefan’s answer below for better code.]:

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

print (n)

``````

2) Why is that code so much faster than this code, which is just to test the speed and has no real purpose other than that?

``````i = 1
while i < 100:
i += 1
``````

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, @quangpn88’s 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
``````

Don’t use this in performance code, but it’s OK for quick tests with moderately large numbers:

``````In : %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 you’re not sure EXACTLY how it works. First of all, this is a great answer to the Project Euler question it stems from. I’ve done a lot of research into this problem and this is by far the simplest response.

For the purpose of explanation, I’ll 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` isn’t 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` doesn’t 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 you’re looking for in a response. If not, let me know and I can explain further.

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, there’s the primefac module which does very large numbers very quickly:

``````#!python

import primefac
import sys

n = int( sys.argv )
factors = list( primefac.primefac(n) )
print 'n'.join(map(str, factors))
``````

For prime number generation I always use `Sieve of Eratosthenes`:

``````def primes(n):
if n<=2:
return []
sieve=[True]*(n+1)
for x in range(3,int(n**0.5)+1,2):
for y in range(3,(n//x)+1,2):
sieve[(x*y)]=False

return +[i for i in range(3,n,2) if sieve[i]]

In : %timeit primes(10**5)
10 loops, best of 3: 60.4 ms per loop

In : %timeit primes(10**6)
1 loops, best of 3: 1.01 s per loop
``````

You can use Miller-Rabin primality test to check whether a number is prime or not. You can find its Python implementations here.

Always use `timeit` module to time your code, the 2nd one takes just `15us`:

``````def func():
n = 600851475143
i = 2
while i * i < n:
while n % i == 0:
n = n / i
i = i + 1

In : %timeit func()
1000 loops, best of 3: 1.35 ms per loop

def func():
i=1
while i<100:i+=1
....:

In : %timeit func()
10000 loops, best of 3: 15.3 us per loop
``````

Isn’t largest prime factor of 27 is 3 ??
The above code might be fastest,but it fails on 27 right ?
27 = 3*3*3
The above code returns 1
As far as I know…..1 is neither prime nor composite

I think, this is the better code

``````def prime_factors(n):
factors=[]
d=2
while(d*d<=n):
while(n>1):
while n%d==0:
factors.append(d)
n=n/d
d+=1
return factors[-1]
``````

``````"""
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

"""

from sympy import primefactors
print primefactors(600851475143)[-1]
``````

``````def find_prime_facs(n):
list_of_factors=[]
i=2
while n>1:
if n%i==0:
list_of_factors.append(i)
n=n/i
i=i-1
i+=1
return list_of_factors
``````

Another way of doing this:

``````import sys
n = int(sys.argv)
result = []
for i in xrange(2,n):
while n % i == 0:
#print i,"|",n
n = n/i
result.append(i)

if n == 1:
break

if n > 1: result.append(n)
print result
``````

sample output :
python test.py 68
[2, 2, 17]