SmexyyWeby

Scripting for Fun and Passion

Python code to calculate the largest prime factor of a large number – Project Euler


I have started using Project Euler recently for fun, and today I was able to solve problem 3 through great help from my friend Sangam.

The problem talks about finding the largest prime factor of a large number. [http://projecteuler.net/problem=3]

ProjectEuler.net

ProjectEuler.net

The solution to the problem might look very trivial through the use of brute force and iterating over all the possible factors of the number and checking if they are prime. However, for very large numbers [if more than 10 digits] this process will fail as the computation will be too long.

To tackle this problem my friend came up with a very intuitive solution which reduces the number of calculations for finding prime and uses few fundamental concepts to reach the solution faster and more efficiently. The assumptions are as follows:

For a given number {n=2^{\alpha}3^{\beta}5^{\gamma}...p^{\kappa}}

  1. Check if the number is divisible by 2, 3 or 5
  2. If it is then strip all the powers of 2, 3, and 5 we are left with all powers of 7, 11, 13 … 29 ….
  3. Now since the LCM of 2, 3, 5 is 30 hence we map all the primes less than 30 excluding 2, 3, 5 and including 1 to all the number greater than 30 as 30+prime_before at same index in the list.
  4. We continue the process of splitting all the powers of the primes which divide the number till we reach a point where only the powers of p are remaining.
  5. Once we split all but one powers of p we are left with n = p which gives us p as the largest prime factor.

The original raw code for this algorithm as written by Sangam can be found at: https://github.com/napsternxg/Project-Euler/blob/master/test.py

The final code after modification and making if modular and efficient is presented below:

The code runs very fast and for a number: 18505779463480206643200 it executes 702 function calls in 0.001 seconds. The detailed results of the profiler can be found at: https://github.com/napsternxg/Project-Euler/blob/master/profile_log.txt

For the above number the profile gave the following output:

############################################################
Profiling started for: [‘largestPrimeFactor.py’, ‘18505779463480206643200’]
Start time: 2012-09-24 03:04:56.384000
All powers of prime factors of 18505779463480206643200 are as follows:
Largest Prime: 823
[[2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096], [3, 9, 27, 81, 243, 729], [5, 25], [7, 49, 343, 2401], [13], [61], [281], [563], [823]]
End time: 2012-09-24 03:04:56.384000
Profiling finished for: [‘largestPrimeFactor.py’, ‘18505779463480206643200’]
############################################################
         702 function calls in 0.001 seconds
   Ordered by: standard name
   ncalls tottime percall cumtime percall filename:lineno(function)
        1 0.000 0.000 0.001 0.001 largestPrimeFactor.py:11(<module>)
      218 0.000 0.000 0.000 0.000 largestPrimeFactor.py:20(nextprime)
      221 0.000 0.000 0.000 0.000 largestPrimeFactor.py:29(checkDivisibility)
      221 0.000 0.000 0.000 0.000 largestPrimeFactor.py:43(updateFactors)
        1 0.000 0.000 0.000 0.000 largestPrimeFactor.py:51(findFactors)
        2 0.000 0.000 0.000 0.000 {built-in method now}
       37 0.000 0.000 0.000 0.000 {method ‘append’ of ‘list’ objects}
        1 0.000 0.000 0.000 0.000 {method ‘disable’ of ‘_lsprof.Profiler’ objects}
If you have suggestions on improving this algorithm or queries regarding its accuracy do write to me in the comment section. Also you can connect with Sangam at: http://www.facebook.com/jain.sangam
My Project Euler repository can be forked from github at: https://github.com/napsternxg/Project-Euler
Happy Coding =)
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: