efficient ways of finding the largest prime factor of a number
Solution 1
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 by13
so now you'll test with830297 / 13 = 63869
-
63869
is still divisible by13
, you are at4913
-
4913
doesn't divide by 13, next prime is17
which divides4913
to get289
-
289
is still a multiple of17
, you have17
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.
Solution 2
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;
}
Solution 3
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.
Solution 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.
Solution 5
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;
}
Zach Smith
I am a Software Developer with experience across a wide range of technologies. I graduated with an MSc in Information Technology from the University of Cape Town, where I worked on alternative methods of scaling traditional (relational) systems using NoSQL data stores. Currently I fulfill the role of a full stack developer, making the most delightful things.
Updated on July 17, 2022Comments
-
Zach Smith almost 2 years
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)
-
Will Ness almost 10 yearsno need to calculate primes though.
-
Padraic Cunningham almost 10 yearsI 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.
-
Will Ness almost 10 yearsno need to pre-calculate primes in this specific problem though. It "involves finding the largest prime factor of a number". Titles, you know...
-
Padraic Cunningham almost 10 yearsI 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".
-
Will Ness almost 10 yearsstarting from
sqrt
down is really bad advice. -
Padraic Cunningham almost 10 yearsYou should post time comparisons and some code. It would be interesting to see it.
-
user448810 almost 10 yearsAs @Will says, you should count up from 2; do not count down from the square root.
-
Will Ness almost 10 years@PadraicCunningham I've edited; you were right, it depends on the specifics of a code.
-
Mihai Maruseac almost 10 yearsFor numbers of form
p*q
wherep
andq
are very close it is not. -
Amy McBlane about 9 yearsJust 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.
-
Toby Speight about 7 yearsWhilst this code snippet is welcome, and may provide some help, it would be greatly improved if it included an explanation 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.