101

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)

#takes about ~0.01secs
  1. 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
#takes about ~3secs
Wolf
  • 9,679
  • 7
  • 62
  • 108
francium
  • 2,384
  • 3
  • 20
  • 29
  • 40
    are you saying the latter takes 3 seconds to iterate from 1 to 100? – Hoopdady Mar 11 '13 at 19:46
  • im as surprised as you are – francium Mar 11 '13 at 19:48
  • 3
    2nd one takes `15.3 us` on my system. – Ashwini Chaudhary Mar 11 '13 at 19:49
  • using the time module before and after the code – francium Mar 11 '13 at 19:52
  • How did you find the time required for running the code? Using timeit.Timer for 1000 times: 0.8454189409967512 for former function 0.011901747959200293 for later (only i+=1) – shantanoo Mar 11 '13 at 19:52
  • 5
    did it feel like it took 3 seconds to run? – Hoopdady Mar 11 '13 at 19:55
  • before i used time module, it did take atleast 2-3 secs, but when i put just a print('start'...'done') before and after, it does it in a fraction of a second anyway, could you please answer the first part of the question – francium Mar 11 '13 at 19:58
  • 1
    For primes generator look [here](http://stackoverflow.com/questions/15319615/prime-number-generator-in-python-accumulation-of-numbers) – f p Mar 11 '13 at 20:06
  • heres the wikipedia article on testing for primality http://en.wikipedia.org/wiki/Primality_test – BloonsTowerDefence Mar 11 '13 at 20:15
  • 3
    Very related questions: http://stackoverflow.com/questions/14138053/project-euler-3-with-python-most-efficient-method, http://stackoverflow.com/questions/14618677/can-someone-check-my-code-for-3-of-project-euler, http://stackoverflow.com/questions/13503320/euler-project-3-in-python, http://stackoverflow.com/questions/12999706/stuck-on-project-euler-3-in-python – poke Mar 11 '13 at 20:15
  • 1
    Project Euler, Problem 3? – Michael David Watson Jan 14 '15 at 17:13
  • Related: http://stackoverflow.com/questions/28248638/what-is-the-logic-of-this-process – GLHF Jan 31 '15 at 05:52
  • Hi! I wanted to ask if you can tell me how to get all of the prime factors? – Adrians Netlis Feb 05 '15 at 12:22
  • See if this helps. This is probably the best https://stackoverflow.com/a/71438297/3204942 – Gary Mar 11 '22 at 12:15

20 Answers20

114

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
Will Ness
  • 70,110
  • 9
  • 98
  • 181
Stefan
  • 4,380
  • 2
  • 30
  • 33
  • should stop when i*i > n. – Will Ness Apr 02 '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 02 '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 03 '14 at 06: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 03 '14 at 06:42
  • in that case, :) I've edited one last correctness fix: 1 is not a prime. – Will Ness Apr 03 '14 at 07:30
  • 3
    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 06:27
  • 2
    Thanks for sharing! Why `n //= i`? I thought `//` is floor division, in this case it should be equivalent to `/`. Is `//` faster than `/`? – YJZ Aug 29 '15 at 08:39
  • @YJZ, yes `//` (`int` division) is faster than `/` (`float` division).. – Liz Av Jan 05 '22 at 19:50
46

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.

Dolph
  • 49,714
  • 13
  • 63
  • 88
Will Luce
  • 1,781
  • 3
  • 20
  • 33
  • 17
    '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
  • 3
    What about the case when `n=4`? This seems like it would print 4 as a prime – alxbl Aug 20 '13 at 06:01
  • 3
    @Mathai I'm guessing Will meant the smallest prime factor, see: http://math.stackexchange.com/questions/102755/greatest-prime-factor-of-n-is-less-than-square-root-of-n-proof – tsiki Dec 10 '13 at 14:11
  • you said that n's largest prime factor is less then the sqrt(n). However in case of 10 it does not work. sqrt(10) = 3.~ but 10 = 2*5 – erogol Jan 08 '14 at 23:24
  • 2
    By this, the largest prime factor of 8 is 1! – Skylar Saveland Feb 24 '14 at 21:36
  • 2
    @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 02 '14 at 20:34
  • 1
    The fixed information: If there is no any factor equal or less then of that number's square root, that number is a prime. – GLHF Jan 31 '15 at 06:13
  • 1
    I'm sorry but can anyone explain to me how to make sure the factors returned in this way are prime number? I can see that they are factors but why didn't the code check that it's prime factor? – Bowen Liu Feb 16 '20 at 23:01
  • 1
    @BowenLiu The smallest factor of a number is always prime, because if it weren't then its factors would also be factors of the number . Since the algorithm only divides out the smallest factor of the current number, all the factors produced are prime. – jodag Mar 07 '22 at 21:31
39

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))
brian d foy
  • 129,424
  • 31
  • 207
  • 592
20

For prime number generation I always use the 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
wjandrea
  • 28,235
  • 9
  • 60
  • 81
Ashwini Chaudhary
  • 244,495
  • 58
  • 464
  • 504
17

If you are looking for pre-written code that is well maintained, use the function sympy.ntheory.primefactors from SymPy.

It returns a sorted list of prime factors of n.

>>> from sympy.ntheory import primefactors
>>> primefactors(6008)
[2, 751]

Pass the list to max() to get the biggest prime factor: max(primefactors(6008))

In case you want the prime factors of n and also the multiplicities of each of them, use sympy.ntheory.factorint.

Given a positive integer n, factorint(n) returns a dict containing the prime factors of n as keys and their respective multiplicities as values.

>>> from sympy.ntheory import factorint
>>> factorint(6008)   # 6008 = (2**3) * (751**1)
{2: 3, 751: 1}

The code is tested against Python 3.6.9 and SymPy 1.1.1.

srikavineehari
  • 2,502
  • 1
  • 11
  • 21
12
"""
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])
Francisco
  • 10,918
  • 6
  • 34
  • 45
11
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
Perviz Mamedov
  • 121
  • 1
  • 5
9

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]
t-8ch
  • 2,583
  • 14
  • 18
m0rpheu5
  • 600
  • 4
  • 16
  • 2
    @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
  • 2
    I know all these things. You didn't seem to know the code does not work. ;-) – mabraham Jun 14 '17 at 20:52
6

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]

Rajesh
  • 179
  • 2
  • 3
5

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)
quangpn88
  • 567
  • 2
  • 7
  • 15
  • 1
    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 02 '14 at 22:35
5

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:
        f.append(n)                 #add last factor...
    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.

Dean Jones
  • 258
  • 4
  • 6
3

In case you want to use numpy here's a way to create an array of all primes not greater than n:

[ i for i in np.arange(2,n+1) if 0 not in np.array([i] * (i-2) ) % np.arange(2,i)]

xenakas
  • 31
  • 1
2

Check this out, it might help you a bit in your understanding.

#program to find the prime factors of a given number
import sympy as smp

try:
    number = int(input('Enter a number : '))
except(ValueError) :
    print('Please enter an integer !')
num = number
prime_factors = []
if smp.isprime(number) :
    prime_factors.append(number)
else :
    for i in range(2, int(number/2) + 1) :   
        """while figuring out prime factors of a given number, n
        keep in mind that a number can itself be prime or if not, 
        then all its prime factors will be less than or equal to its int(n/2 + 1)"""
        if smp.isprime(i) and number % i == 0 :
            while(number % i == 0) :
                prime_factors.append(i)
                number = number  / i
print('prime factors of ' + str(num) + ' - ')
for i in prime_factors :
    print(i, end = ' ')

enter image description here

kumabis4u
  • 51
  • 4
2

This is my python code: it has a fast check for primes and checks from highest to lowest the prime factors. You have to stop if no new numbers came out. (Any ideas on this?)

import math


def is_prime_v3(n):
    """ Return 'true' if n is a prime number, 'False' otherwise """
    if n == 1:
        return False

    if n > 2 and n % 2 == 0:
        return False

    max_divisor = math.floor(math.sqrt(n))
    for d in range(3, 1 + max_divisor, 2):
        if n % d == 0:
            return False
    return True


number = <Number>

for i in range(1,math.floor(number/2)):
    if is_prime_v3(i):
        if number % i == 0:
            print("Found: {} with factor {}".format(number / i, i))

The answer for the initial question arrives in a fraction of a second.

ThorstenC
  • 1,264
  • 11
  • 26
0

Below are two ways to generate prime factors of given number efficiently:

from math import sqrt


def prime_factors(num):
    '''
    This function collectes all prime factors of given number and prints them.
    '''
    prime_factors_list = []
    while num % 2 == 0:
        prime_factors_list.append(2)
        num /= 2
    for i in range(3, int(sqrt(num))+1, 2):
        if num % i == 0:
            prime_factors_list.append(i)
            num /= i
    if num > 2:
        prime_factors_list.append(int(num))
    print(sorted(prime_factors_list))


val = int(input('Enter number:'))
prime_factors(val)


def prime_factors_generator(num):
    '''
    This function creates a generator for prime factors of given number and generates the factors until user asks for them.
    It handles StopIteration if generator exhausted.
    '''
    while num % 2 == 0:
        yield 2
        num /= 2
    for i in range(3, int(sqrt(num))+1, 2):
        if num % i == 0:
            yield i
            num /= i
    if num > 2:
        yield int(num)


val = int(input('Enter number:'))
prime_gen = prime_factors_generator(val)
while True:
    try:
        print(next(prime_gen))
    except StopIteration:
        print('Generator exhausted...')
        break
    else:
        flag = input('Do you want next prime factor ? "y" or "n":')
        if flag == 'y':
            continue
        elif flag == 'n':
            break
        else:
            print('Please try again and enter a correct choice i.e. either y or n')
G.G.
  • 592
  • 5
  • 16
0

Since nobody has been trying to hack this with old nice reduce method, I'm going to take this occupation. This method isn't flexible for problems like this because it performs loop of repeated actions over array of arguments and there's no way how to interrupt this loop by default. The door open after we have implemented our own interupted reduce for interrupted loops like this:

from functools import reduce

def inner_func(func, cond, x, y):
    res = func(x, y)
    if not cond(res):
        raise StopIteration(x, y)
    return res

def ireducewhile(func, cond, iterable):
    # generates intermediary results of args while reducing
    iterable = iter(iterable)
    x = next(iterable)
    yield x
    for y in iterable:
        try:
            x = inner_func(func, cond, x, y)
        except StopIteration:
            break
        yield x

After that we are able to use some func that is the same as an input of standard Python reduce method. Let this func be defined in a following way:

def division(c):
    num, start = c
    for i in range(start, int(num**0.5)+1):
        if num % i == 0:
            return (num//i, i)
    return None

Assuming we want to factor a number 600851475143, an expected output of this function after repeated use of this function should be this:

(600851475143, 2) -> (8462696833 -> 71), (10086647 -> 839), (6857, 1471) -> None

The first item of tuple is a number that division method takes and tries to divide by the smallest divisor starting from second item and finishing with square root of this number. If no divisor exists, None is returned. Now we need to start with iterator defined like this:

def gener(prime):
    # returns and infinite generator (600851475143, 2), 0, 0, 0...
    yield (prime, 2)
    while True:
        yield 0

Finally, the result of looping is:

result = list(ireducewhile(lambda x,y: div(x), lambda x: x is not None, iterable=gen(600851475143)))
#result: [(600851475143, 2), (8462696833, 71), (10086647, 839), (6857, 1471)]

And outputting prime divisors can be captured by:

if len(result) == 1: output = result[0][0]
else: output = list(map(lambda x: x[1], result[1:]))+[result[-1][0]]
#output: [2, 71, 839, 1471]

Note:

In order to make it more efficient, you might like to use pregenerated primes that lies in specific range instead of all the values of this range.

mathfux
  • 5,759
  • 1
  • 14
  • 34
0
from functools import lru_cache

primes = []


@lru_cache(maxsize=None)
def factors(n: int):
    if n < 2:
        return
    factors(int(n ** 0.5))

    for prime in primes:
        if n % prime == 0:
            return sorted((prime, *factors(n // prime)))

    primes.append(n)
    return [n]


if __name__ == '__main__':
    print(factors(680000))
    print(factors(600851475143))

Output

[2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 17]
[600851475143]
Semnodime
  • 1,872
  • 1
  • 15
  • 24
-1

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.

rubslopes
  • 15
  • 2
  • 1
    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 02 '14 at 20:16
-1
def prime(n):
    for i in range(2,n):
        if n%i==0:
            return False
    return True

def primefactors():
    m=int(input('enter the number:'))
    for i in range(2,m):
        if (prime(i)):
            if m%i==0:
                print(i)
    return print('end of it')

primefactors()
camba1
  • 1,795
  • 2
  • 12
  • 18
  • 1
    In general it is good practice to a at least a small comment about what your solution is doing. In particular for this question, you should specify that you are answering just part of the question (part 1). – camba1 Jun 15 '19 at 12:16
  • 1
    This code is incorrect for prime numbers (it should output the number itself) – xmcp Jul 28 '20 at 07:21
-2

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
madGambol
  • 15
  • 2