Effective Ways to Find the Largest Prime Multiplier

Question

I am doing this problem on the site that I found (Euler project), and a question arises that involves finding the largest prime number. My solution crashes on very large quantities, so I was wondering how this code can be simplified?

""" 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 assume. (computer traffic jams, tells me that I have run out of memory and asks which programs I would like to stop).

************************************** Thank you for the answer, in any case there were actually several errors in code. therefore, a fixed version of this (inefficient code) is lower.

 """ 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) 

Answer 1

From your approach, you first generate all the divisors of the number n in O(n) , then you check which of these divisors is a simple number of O(n) calls to test_prime (which is exponential anyway).

The best approach is to notice that as soon as you find out about the number divider, you can divide it in order to get rid of all its factors. Thus, to get prime odds, say 830297 , you check all the small primes (cached) and for each one that divides your number, which you continue to divide:

• 830297 is divisible by 13 , so now you will test with 830297 / 13 = 63869
• 63869 is still divided by 13 , you are at 4913
• 4913 does not divide by 13, the next prime number is 17 , which divides 4913 into 289
• 289 is still a multiple of 17 , you have 17 , which is a divisor and stops.

---

To further increase the speed, after testing the cached primes below, say 100 , you will need to check the prime divisors using your test_prime function (updated according to @Ben's answer), but continue the opposite starting with sqrt . Your number is divided by 71 , the next number will give sqrt of 91992 , which is somewhat close to 6857 , which is the biggest simple factor.

Answer 2

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 the main wheel to generate trial factors. It is not as fast as trial division into primes, but there is no need to calculate or store primes, therefore it is very convenient.

If you are interested in programming prime numbers, you can enjoy this essay on my blog.

Answer 3

My solution is in C #. I bet you can translate it into python. I tested it with a random long integer from 1 to 1.000.000.000, which is good. You can try to check the result using the online main 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; } 

Answer 4

A naive primitive test can be improved in several ways:

• Test divisibility by 2 separately, then run your loop at 3 and go to 2
• End the loop in ceil (sqrt (num)). You are guaranteed not to find the main odds above this number.
• Generate prime numbers using a sieve in advance, and only move naively if you have exhausted the numbers in the sieve.

Beyond these simple fixes, you'll have to look for more efficient factorization algorithms.

Answer 5

Use the Sieve of Eratosthenes to calculate your prime numbers.

 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) 

Answer 6

The point to simple factorization by trial division is the most effective solution for factorizing only one number, it does not require any simple testing.

You simply list your possible factors in ascending order and continue to separate them by the amount in question - all of which, in this way, guaranteed factors guarantee that they will be the main ones. Stop when the square of the current coefficient exceeds the current factorized number. See code in user448810 answer .

Usually simple factorization by trial division is faster on primes than on all numbers (or coefficients, etc.), but if you decompose only one number, to find primes first to check their separation, it can cost more than just go ahead with an increase in the flow of possible factors. This listing is O (n), the primary generation is O (n log log n), Sieve of Eratosthenes (SoE) , where n = sqrt (N) for the upper limit of N. With trial division (TD), the complexity is O (n ^1,5 / (log n) ² ) i>.

Of course, asymptotics should be taken as a guide; actual code constants can change the picture. Example, runtime for Haskell code obtained from here and here , factorization 600851475149 (simple):

 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, the factorization of the composite number in question, 600851475143, is almost instantaneous, so it doesn’t matter there.

Answer 7

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; } 

Answer 8

I converted the solution from @ under5hell to Python (2.7x). what an effective 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 

Answer 9

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) 

Answer 10

Old but can 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) 

Answer 11

Hope this helps and is 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)