efficient ways of finding the largest prime factor of a number

Question

I'm doing this problem on a site that I found (project Euler), and there is a question that involves finding the largest prime factor of a number. My solution fails at really large numbers so I was wondering how this code could be streamlined?

""" Find the largest prime of a number """


def get_factors(number):
    factors = []
    for integer in range(1, number + 1):
        if number%integer == 0:
            factors.append(integer)
    return factors

def test_prime(number):
    prime = True
    for i in range(1, number + 1):
        if i!=1 and i!=2 and i!=number:
            if number%i == 0:
                prime = False
    return prime

def test_for_primes(lst):
    primes = []
    for i in lst:
        if test_prime(i):
            primes.append(i)
    return primes


################################################### program starts here
def find_largest_prime_factor(i):
    factors = get_factors(i)
    prime_factors = test_for_primes(factors)
    print prime_factors


print find_largest_prime_factor(22)

#this jams my computer
print find_largest_prime_factor(600851475143)

it fails when using large numbers, which is the point of the question I guess. (computer jams, tells me I have run out of memory and asks me which programs I would like to stop).

************************************ thanks for the answer. there was actually a couple bugs in the code in any case. so the fixed version of this (inefficient code) is below.

""" Find the largest prime of a number """


def get_factors(number):
    factors = []
    for integer in xrange(1, number + 1):
        if number%integer == 0:
            factors.append(integer)
    return factors

def test_prime(number):
    prime = True
    if number == 1 or number == 2:
        return prime
    else:
        for i in xrange(2, number):
            if number%i == 0:
                prime = False
    return prime


def test_for_primes(lst):
    primes = []
    for i in lst:
        if test_prime(i):
            primes.append(i)
    return primes


################################################### program starts here
def find_largest_prime_factor(i):
    factors = get_factors(i)
    print factors
    prime_factors = test_for_primes(factors)
    return prime_factors


print find_largest_prime_factor(x)

what's the difference between the logic of the two functions? — Zach Smith, Jun 11 '14 at 15:14
also check [this thread](http://stackoverflow.com/questions/23287/largest-prime-factor-of-a-number) — agamike, Jun 11 '14 at 15:14
`range(600851475143)` will take up at least 600851475143 x 4 bytes of memory. `xrange` won't (assuming python2). — georg, Jun 11 '14 at 15:16
out of curiosity, which question is this? Just noting that after about problem 100 or so, the numbers in the questions become ridiculously huge — Ben, Jun 11 '14 at 15:17
if speaking on **efficient** ways I'd suggest to read basics, eg. starting from [wiki Integer factorization](http://en.wikipedia.org/wiki/Integer_factorization). The straight way you do you would run either of memory or of time. — agamike, Jun 11 '14 at 15:25
@Ben. question3. just found the resource the other day. could be fun.. — Zach Smith, Jun 11 '14 at 15:29
@ZachSmith I love project euler, as a math major. It's still early enough in the problem sets that most numbers can be contained in native data types, which is what I was wondering about. — Ben, Jun 11 '14 at 15:32
@WillNess **1st** I'm really sorry as I'm novice here and do not understand up/down votes' economy here, and would be grateful if **2nd** you hint on the right policy guidelines here Will. Regards, M. — agamike, Jun 11 '14 at 21:06

score 6 · Accepted Answer · answered Jun 11 '14 at 15:29

From your approach you are first generating all divisors of a number n in O(n) then you test which of these divisors is prime in another O(n) number of calls of test_prime (which is exponential anyway).

A better approach is to observe that once you found out a divisor of a number you can repeatedly divide by it to get rid of all of it's factors. Thus, to get the prime factors of, say 830297 you test all small primes (cached) and for each one which divides your number you keep dividing:

830297 is divisible by 13 so now you'll test with 830297 / 13 = 63869
63869 is still divisible by 13, you are at 4913
4913 doesn't divide by 13, next prime is 17 which divides 4913 to get 289
289 is still a multiple of 17, you have 17 which is the divisor and stop.

For further speed increase, after testing the cached prime numbers below say 100, you'll have to test for prime divisors using your test_prime function (updated according to @Ben's answer) but go on reverse, starting from sqrt. Your number is divisible by 71, the next number will give an sqrt of 91992 which is somewhat close to 6857 which is the largest prime factor.

As @Will says, you should count up from 2; do _not_ count down from the square root. — user448810, Jun 11 '14 at 23:21
For numbers of form `p*q` where `p` and `q` are very close it is not. — Mihai Maruseac, Jun 13 '14 at 08:20

score 5 · Answer 2 · answered Jun 11 '14 at 17:43

Here is my favorite simple factoring program for Python:

def factors(n):
    wheel = [1,2,2,4,2,4,2,4,6,2,6]
    w, f, fs = 0, 2, []
    while f*f <= n:
        while n % f == 0:
            fs.append(f)
            n /= f
        f, w = f + wheel[w], w+1
        if w == 11: w = 3
    if n > 1: fs.append(n)
    return fs

The basic algorithm is trial division, using a prime wheel to generate the trial factors. It's not quite as fast as trial division by primes, but there's no need to calculate or store the prime numbers, so it's very convenient.

If you're interested in programming with prime numbers, you might enjoy this essay at my blog.

score 5 · Answer 3 · answered Jun 12 '15 at 05:42

My solution is in C#. I bet you can translate it into python. I've been test it with random long integer ranging from 1 to 1.000.000.000 and it's doing good. You can try to test the result with online prime calculator Happy coding :)

public static long biggestPrimeFactor(long num) {
    for (int div = 2; div < num; div++) {
        if (num % div == 0) {
            num \= div
            div--;
        }
    }
    return num;
}

score 4 · Answer 4 · answered Jun 11 '14 at 15:16

4

The naive primality test can be improved upon in several ways:

Test for divisibility by 2 separately, then start your loop at 3 and go by 2's
End your loop at ceil(sqrt(num)). You're guaranteed to not find a prime factor above this number
Generate primes using a sieve beforehand, and only move onto the naive way if you've exhausted the numbers in your sieve.

Beyond these easy fixes, you're going to have to look up more efficient factorization algorithms.

answered Jun 11 '14 at 15:16

Ben

2,065
1
13
19

1

Just a clarification of 2 above: there CAN be prime factors above ceil(sqrt(num)). Example: 3*13 = 39, ceil(sqrt(39)) = 7. Of course if you've already found 3, then you've probably eliminated 13. – Amy McBlane Mar 01 '15 at 00:45

score 3 · Answer 5 · answered Jun 11 '14 at 15:29

3

Use a Sieve of Eratosthenes to calculate your primes.

from math import sqrt

def sieveOfEratosthenes(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)
    return filter(None, primes)

answered Jun 11 '14 at 15:29

Padraic Cunningham

176,452
29
245
321

[no need to calculate primes](http://stackoverflow.com/a/24171827/849891) though. – Will Ness Jun 11 '14 at 20:28
I did the problem in Euler using the code above with a another simple function and it is certainly efficient in finding prime factors. The OP's question title is "efficient ways of finding primes and factors", I think my sieve is efficient. – Padraic Cunningham Jun 11 '14 at 20:46
no need to pre-calculate primes in this specific problem though. It "involves finding the largest prime factor of a number". Titles, you know... – Will Ness Jun 11 '14 at 20:48
I mainly posted as later on in Euler, having a good way to calculate primes will certainly be useful and avoid another title that includes "efficient ways of finding primes". – Padraic Cunningham Jun 11 '14 at 20:51

score 3 · Answer 6 · edited May 23 '17 at 12:02

The point to prime factorization by trial division is, the most efficient solution for factorizing just one number doesn't need any prime testing.

You just enumerate your possible factors in ascending order, and keep dividing them out of the number in question - all thus found factors are guaranteed to be prime. Stop when the square of current factor exceeds the current number being factorized. See the code in user448810's answer.

Normally, prime factorization by trial division is faster on primes than on all numbers (or odds etc.), but when factorizing just one number, to find the primes first to test divide by them later, ~~will~~ might cost more than just going ahead with the increasing stream of possible factors. This enumeration is O(n), prime generation is O(n log log n), with the Sieve of Eratosthenes (SoE), where n = sqrt(N) for the top limit N. With trial division (TD) the complexity is O(n^1.5/(log n)²).

Of course the asymptotics are to be taken just as a guide, actual code's constant factors might change the picture. Example, execution times for a Haskell code derived from here and here, factorizing 600851475149 (a prime):

2..                       0.57 sec
2,3,5,...                 0.28 sec
2,3,5,7,11,13,17,19,...   0.21 sec
primes, segmented TD      0.65 sec    first try
                          0.05 sec    subsequent runs (primes are memoized)
primes, list-based SoE    0.44 sec    first try
                          0.05 sec    subsequent runs (primes are memoized)
primes, array-based SoE   0.15 sec    first try
                          0.06 sec    subsequent runs (primes are memoized)

so it depends. Of course factorizing the composite number in question, 600851475143, is near instantaneous, so it doesn't matter there.

You should post time comparisons and some code. It would be interesting to see it. — Padraic Cunningham, Jun 11 '14 at 21:06
@PadraicCunningham I've edited; you were right, it depends on the specifics of a code. — Will Ness, Jun 12 '14 at 16:21

score 3 · Answer 7 · edited May 23 '17 at 12:02

3

Here is an example in JavaScript

function largestPrimeFactor(val, divisor = 2) { 
    let square = (val) => Math.pow(val, 2);

    while ((val % divisor) != 0 && square(divisor) <= val) {
        divisor++;
    }

    return square(divisor) <= val
        ? largestPrimeFactor(val / divisor, divisor)
        : val;
}

edited May 23 '17 at 12:02

Community

1
1

answered Apr 01 '16 at 15:58

Vlad Bezden

83,883
25
248
179

score 1 · Answer 8 · answered Feb 12 '17 at 18:52

I converted the solution from @under5hell to Python (2.7x). what an efficient way!

def largest_prime_factor(num, div=2):
    while div < num:
        if num % div == 0 and num/div > 1:
            num = num /div
            div = 2
        else:
            div = div + 1
    return num
>> print largest_prime_factor(600851475143)
6857
>> print largest_prime_factor(13195)
29

score 1 · Answer 9 · edited May 04 '17 at 13:44

1

Try this piece of code:

from math import *

def largestprime(n):
    i=2
    while (n>1):
        if (n % i == 0):
            n = n/i
        else:
            i=i+1
    print i     

strinput = raw_input('Enter the number to be factorized : ')
a = int(strinput)
largestprime(a)

edited May 04 '17 at 13:44

Billal Begueradj

20,717
43
112
130

answered Mar 21 '17 at 13:40

newbie101

11
2

2

Whilst this code snippet is welcome, and may provide some help, it would be [greatly improved if it included an explanation](//meta.stackexchange.com/q/114762) of *how* and *why* this solves the problem. Remember that you are answering the question for readers in the future, not just the person asking now! Please [edit] your answer to add explanation, and give an indication of what limitations and assumptions apply. – Toby Speight Mar 21 '17 at 13:46

score 0 · Answer 10 · answered Jan 02 '17 at 16:35

Old one but might help

def isprime(num):
    if num > 1:
        # check for factors
        for i in range(2,num):
                if (num % i) == 0:
                    return False 
        return True

def largest_prime_factor(bignumber):
    prime = 2
    while bignumber != 1:
        if bignumber % prime == 0:
            bignumber = bignumber / prime
        else:
            prime = prime + 1
            while isprime(prime) == False:
                prime = prime+1
    return prime
number = 600851475143
print largest_prime_factor(number)

score 0 · Answer 11 · answered Mar 15 '17 at 18:59

0

I Hope this would help and easy to understand.

A = int(input("Enter the number to find the largest prime factor:"))

B = 2

while (B <(A/2)):

    if A%B != 0:
        B = B+1

    else:
        A = A/B
        C = B
        B = 2
print (A)

answered Mar 15 '17 at 18:59

Pritesh

1

dilson torrefiel · Answer 12 · 2018-04-05T15:54:23.170

This code for getting the largest prime factor, with nums value of prime_factor(13195) when I run it, will return the result in less than a second. but when nums value gets up to 6digits it will return the result in 8seconds.

Any one has an idea of what is the best algorithm for the solution...

def prime_factor(nums):

if nums < 2:
    return 0
primes = [2]
x = 3
while x <= nums:
    for i in primes:
        if x%i==0:
            x += 2
            break
    else:
        primes.append(x)
        x += 2
largest_prime = primes[::-1]
# ^^^ code above to gets all prime numbers

intermediate_tag = []
factor = []
# this code divide nums by the largest prime no. and return if the
# result is an integer then append to primefactor.
for i in largest_prime:
    x = nums/i
    if x.is_integer():
        intermediate_tag.append(x)

# this code gets the prime factors [29.0, 13.0, 7.0, 5.0]     
for i in intermediate_tag:
    y = nums/i
    factor.append(y)



print(intermediate_tag)
print(f"prime factor of {nums}:==>",factor)

prime_factor(13195)

[455.0, 1015.0, 1885.0, 2639.0] prime factor of 13195:==> [29.0, 13.0, 7.0, 5.0]

efficient ways of finding the largest prime factor of a number

12 Answers12

Linked