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