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

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

- Check if the number is divisible by 2, 3 or 5
- If it is then strip all the powers of 2, 3, and 5 we are left with all powers of 7, 11, 13 … 29 ….
- 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.
- 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.
- 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
Happy Coding =)

### Like this:

Like Loading...

*Related*