# Python Finding Prime Factors

Two part question...

1) Trying to determine the largest prime factor of 600851475143, found this program online that seems to work, the problem is im having a hard time figuring out how it works exactly (i understand the basics of what the program is doing)...also if you could shed some light on any method you may know of finding prime (perhaps without testing every number) and how you method works.

The code that i found online for prime factor

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

print (n)

``````

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

``````i = 1
while i < 100:
i += 1
``````
• are you saying the latter takes 3 seconds to iterate from 1 to 100? – Hoopdady Mar 11 '13 at 19:46
• 2nd one takes `15.3 us` on my system. – Ashwini Chaudhary Mar 11 '13 at 19:49
• how are you measuring the time? – Hoopdady Mar 11 '13 at 19:50
• For primes generator look here – f p Mar 11 '13 at 20:06
• – poke Mar 11 '13 at 20:15

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 [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
``````
• should stop when i*i > n. – Will Ness Apr 2 '14 at 20:15
• @WillNess: Agreed. In the meanwhile, I believe I found a way to achieve both correctness and early termination. Updated my answer. – Stefan Apr 2 '14 at 22:27
• great. you can get rid of `max` call if you'd turn the inner `while` into a simple `if (n%i==0): n //= i; else: i+=1`. – Will Ness Apr 3 '14 at 6:09
• @WillNess: Yes, this works and (somewhat surprisingly) is faster, at the expense of 1 more line of code in standard Python formatting. Updated my answer again. Next big thing to trade lines of code into speed would be to separate out the case `i = 2` and then use `i += 2` from `i = 3` on. But I'll leave it there. I was just concerned that the first link on Google yielded a wrong algorithm... – Stefan Apr 3 '14 at 6:42
• For odd numbers, you could do `i += 2` instead of 1, and start with `i = 3` instead of 2. Don't know how much of a performance difference that would make. – rvighne Nov 11 '14 at 6:27

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.

• 'because the largest prime factor will never be larger than the square root of n' - why? largest prime factor of 10 is 5, and 5 is greater than the square root of 10 – Mathai Aug 14 '13 at 20:13
• What about the case when `n=4`? This seems like it would print 4 as a prime – alxbl Aug 20 '13 at 6:01
• @Mathai I'm guessing Will meant the smallest prime factor, see: math.stackexchange.com/questions/102755/… – tsiki Dec 10 '13 at 14:11
• By this, the largest prime factor of 8 is 1! – Skylar Saveland Feb 24 '14 at 21:36
• @Mathai because we divide the divisors out of the number, we can stop when i*i > n. Then the last `n` is the biggest factor of the original number (if we replace the inner `while` with an `if`: `if n%i==0: n=n/i else: i=i+1`). – Will Ness Apr 2 '14 at 20:34

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[1] )
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 [2]+[i for i in range(3,n,2) if sieve[i]]

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

In [43]: %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 [19]: %timeit func()
1000 loops, best of 3: 1.35 ms per loop

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

In [21]: %timeit func()
10000 loops, best of 3: 15.3 us per loop
``````
• `gmpy2` also has a fast Miller-Rabin implementation – John La Rooy Dec 21 '15 at 23:43

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]
``````
• Doesn't work for 1, 2, or 3 – mabraham Jun 13 '17 at 20:10
• @mabraham As I have mentioned above, 1 is neither prime nor composite !! And it doesn't work for 2,3 because d starts from 2 !! so we can add an if condition there !! – m0rpheu5 Jun 14 '17 at 20:34
• I know all these things. You didn't seem to know the code does not work. ;-) – mabraham Jun 14 '17 at 20:52

The code is wrong with 100. It should check case i * i = n:

I think it should be:

``````while i * i <= n:
if i * i = n:
n = i
break

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

print (n)
``````
• Unfortunately, this still doesn't work if the largest prime factor occurs 3 or more times (e.g. `n = 8`). See my answer for a fix. – Stefan Apr 2 '14 at 22:35

Another way of doing this:

``````import sys
n = int(sys.argv[1])
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]

``````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
``````
• Please provide some explanation for your code – thumbtackthief Oct 19 '17 at 14:57
• my code gives factors not multiples – Perviz Mamedov Oct 31 '17 at 8:26

You shouldn't loop till the square root of the number! It may be right some times, but not always!

Largest prime factor of 10 is 5, which is bigger than the sqrt(10) (3.16, aprox).

Largest prime factor of 33 is 11, which is bigger than the sqrt(33) (5.5,74, aprox).

You're confusing this with the propriety which states that, if a number has a prime factor bigger than its sqrt, it has to have at least another one other prime factor smaller than its sqrt. So, with you want to test if a number is prime, you only need to test till its sqrt.

• wrong. you should loop for i=2... and stop when i*i > n. You just need to adjust what you return in which case. This works for your examples either because we divide out each divisor from the number. – Will Ness Apr 2 '14 at 20:16

My code:

``````# METHOD: PRIME FACTORS
def prime_factors(n):
'''PRIME FACTORS: generates a list of prime factors for the number given
RETURNS: number(being factored), list(prime factors), count(how many loops to find factors, for optimization)
'''
num = n                         #number at the end
count = 0                       #optimization (to count iterations)
index = 0                       #index (to test)
t = [2, 3, 5, 7]                #list (to test)
f = []                          #prime factors list
while t[index] ** 2 <= n:
count += 1                  #increment (how many loops to find factors)
if len(t) == (index + 1):
t.append(t[-2] + 6)     #extend test list (as much as needed) [2, 3, 5, 7, 11, 13...]
if n % t[index]:            #if 0 does else (otherwise increments, or try next t[index])
index += 1              #increment index
else:
n = n // t[index]       #drop max number we are testing... (this should drastically shorten the loops)
f.append(t[index])      #append factor to list
if n > 1:
return num, f, f'count optimization: {count}'
``````

Which I compared to the code with the most votes, which was very fast

``````    def prime_factors2(n):
i = 2
factors = []
count = 0                           #added to test optimization
while i * i <= n:
count += 1                      #added to test optimization
if n % i:
i += 1
else:
n //= i
factors.append(i)
if n > 1:
factors.append(n)
return factors, f'count: {count}'   #print with (count added)
``````

TESTING, (note, I added a COUNT in each loop to test the optimization)

``````# >>> prime_factors2(600851475143)
# ([71, 839, 1471, 6857], 'count: 1472')
# >>> prime_factors(600851475143)
# (600851475143, [71, 839, 1471, 6857], 'count optimization: 494')
``````

I figure this code could be modified easily to get the (largest factor) or whatever else is needed. I'm open to any questions, my goal is to improve this much more as well for larger primes and factors.

Another way that skips even numbers after 2 is handled:

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

return factors
``````
``````"""
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]
``````

Do the following:

``````def primefactors(n):
return filter(lambda x:n%x==0, range(2, int(floor(sqrt(n)))))
``````
• This doesn't work. `primefactors(6)` returns `[]` and `primefactors(32)` returns `[2, 4]`, both of which are wrong. It should be `[2, 2]` and `[2, 2, 2, 2, 2]`. – Elmar Peise Dec 5 '16 at 23:19
``````n=int(input("Enter the number"))
if n==1 :  #because the below logic doesn't work on 1
print(n)
for i in range(2 , n+1):
if n%i==0 :
n1=i  #get factor
for b in range(2,n+1): #check if it is prime
if ((n1%b)==0) & (n1==b):
print(n1)
elif (n1%b)==0 or n1<b:  #if not then pass
break
``````

i am sure this is the worst logic but it's all the knowledge i have in .py this program will get a number from user and prints all of it's factors numbers that are prime like for 12 it will give 2,3

• Can you explain your code a bit, so that others can understand it better? – Robert Mar 18 '17 at 20:33
• just edited if still not clear i can try harder – Muhammad Yusuf Mar 18 '17 at 20:35
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}