Problem: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?

Solutions: I’ll give a Sage, Python, Cython and C solution.

### Sage Solution

There is a single-line solution in Sage.

sage: max(ZZ(600851475143).prime_factors()) 6857

Let’s time this with 100,000 iterations in Sage.

import time   start = time.time() for i in range(100000): a = max(ZZ(600851475143).prime_factors()) elapsed = (time.time() - start)   print "result %s returned after %s seconds (100,000 iterations)." % (a, elapsed)

We get the following result.

result 6857 returned after 4.41913223267 seconds (100,000 iterations).

So, the calculation in Sage averages somewhere around 4.42e-05 seconds. That’s relatively quick. Let’s now write our own Python code.

### Python Solution

We’ll start factoring an input number by removing multiples of 2. Then, we’ll look at odd integers in increasing value until the number is completely factored. This is far from the most efficient factorization algorithm, but it will work. And, since we’re only interested in the largest factor, we don’t need to store much in memory.

import time   def largest_prime_factor(n):   largest_factor = 1   # remove any factors of 2 first while n % 2 == 0: largest_factor = 2 n = n/2   # now look at odd factors p = 3 while n != 1: while n % p == 0: largest_factor = p n = n/p p += 2   return largest_factor   start = time.time() for i in range(100000): a = largest_prime_factor(600851475143) elapsed = (time.time() - start)   print "result %s returned after %s seconds (100,000 iterations)." % (a, elapsed)

We get the following result.

result 6857 returned after 93.1715428829 seconds (100,000 iterations).

This means that each iteration takes roughly 0.0009317 seconds, or about 21 times the time of the Sage code above. This makes sense here as the Sage code is using a much more efficient factorization algorithm. What happens when we code our Python into Cython?

### Cython Solution

We’ll modify our Python code to Cython and see how fast it runs.

%cython   import time   cdef largest_prime_factor(unsigned long n):   cdef unsigned long largest_factor = 1 cdef unsigned long p = 3   # remove any factors of 2 first while n % 2 == 0: largest_factor = 2 n = n/2   # now look at odd factors while n != 1: while n % p == 0: largest_factor = p n = n/p p += 2   return largest_factor   start = time.time() for i in range(100000): a = largest_prime_factor(600851475143) elapsed = (time.time() - start)   print "result %s returned after %s seconds (100,000 iterations)." % (a, elapsed)

This returns the following result when executed.

result 6857 returned after 5.63884592056 seconds (100,000 iterations).

The Cython code is roughly 16.523 times faster than the Python code. The Cython code still takes roughly 27% longer than the Sage code, which is fine since Sage is using the PARI C library for factorizations, and our code was relatively cheap. For how much effort was put in to writing the Cython code, it performs very well. We can make this faster by writing the same code in C.

### C Solution

The C code here has the same basic structure as the Python and Cython code.

#include <stdio.h> #include <stdlib.h>   unsigned long largest_prime_factor(unsigned long n) { unsigned long largest_factor = 1; unsigned long p = 3; unsigned long div = n;   /* remove any factors of 2 first */ while (div % 2 == 0) { largest_factor = 2; div = div/2; }   /* now look at odd factors */ while (div != 1) { while (div % p == 0) { largest_factor = p; div = div/p; } p = p + 2; }   return largest_factor; }   int main(int argc, char **argv) { unsigned long factor; unsigned long max = 100000; unsigned long i = 1;   while (i <= max) { factor = largest_prime_factor(600851475143); i++; } printf("%ld\n", factor);   return 0; }

We compile (with GCC) and then run the executable (which includes 100000 iterations of the required function) to find that it takes 2.576 seconds, which is about 58% the runtime of the original Sage code.

Comments are closed