0x0003 - Project Euler 003

Problem:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Solution:

1. A neat little trick for Linux/UNIX users in Python is:

from commands import *
print int(getoutput("factor 600851475143").split()[::-1][0])

2. But a general program could be:

p, n = 2, 600851475143

while (p*p <= n) :
  if (n % p == 0) :
    n /= p
  if p == 2: p += 1
  else: p += 2

print n

Analysis:

I have solved this problem in two ways using Python 2.7 in Ubuntu 10.10. In the first code, initially I’ve imported all methods from the ‘commands’ module in Python, using which I can run Operating System(OS) commands and get the result from within my Python program. The next line is where the “cheat” lies.

The ‘getoutput()‘ method takes as argument, the Linux/UNIX command in the form of a string, and it returns the output of the command as another string. In this case I pass the string “factor 600851475143” as argument, where ‘factor’ is the Linux/UNIX command.

You can use the command “man factor” to see how factor is used at your site. The full documentation for factor is maintained as a Texinfo manual. If the info and factor programs are properly installed at your site, the command “info coreutils ‘factor invocation’” should give you access to the complete manual.

So the method getoutput(“factor 600851475143”) returns a string containing the passed number, followed by a series of prime factors in ascending order, separated by a space. Applying the split() method on the result gives a list of strings in the same order of occurrence as in the command output. Applying the ‘[::-1]’ to it simply reverses the list, thus converting to one having strings in descending order. Then the string at the first index is retrieved by adding [0] at the end. Finally the int() converts the largest prime factor from a string to an integer and it is printed to the standard output.

However, this method has two disadvantages: one, that it can only be run on UNIX based systems, and two, that it cannot find factors for numbers larger than 264.

In the second code, I have initialized two variables ‘p‘ (first prime number) and ‘n‘ (number to be factorized). In the program, n will be divided until it is no longer divisible by p, which is being incremented.

The terminating condition for the while loop is when p*p exceeds n, i.e. p is more than the square of n, in which case n is the largest prime factor. The first if loop within the while loop divides n by p. This means that if n is evenly divisible by any p, then n is not a prime number. So, dividing n by p will move us one step closer to modifying n to its largest prime factor. Now, if we increment p by 1 after every loop, then it will take a very long time to compute the result. Instead, we can increment p so that it is always odd. Also, as 2 is the only even prime, we need to increment p by 1 to make it the next odd number (3). This is clearly written in the if-else statement. Finally, the result is the modified value of n.

The first code ran in about 2.295 milliseconds. The second one had a run-time of 0.607 milliseconds.