Was it cheating?
2 min read

Was it cheating?

I was looking into the Project Euler's problem list and I soon reached the third one, "Largest prime factor":

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

What is the largest prime factor of the number 600851475143 ?

I began coding a rather straightforward solution, involving some divisor loops and a prime tester and began iterating. Of course, I added some performance improvements, like checking for even numbers and only searching for odd numbers, since with the exception of 2, all prime numbers are odd. Then I very confidently ran the python script.

An hour later the script was still running and out of my 8 gigabytes of RAM I had close to none left... I was forced to force-quit Python and found myself nowhere near a solution.

So enters plan B: let's search for some algorithms and ideas on the Internet. Of course, a complete solution was not desirable. I wanted to do it by myself, as much as it was possible and copy-pasting an answer was no fun.

And there I was, reading a helpful thread on StackOverflow, and looking into the algorithms. And it did not went well... I was left perplexed by the math behind them. There were all these fancy-named solution, involving math algorithms and I felt out of my league. It was depressing, to be honest.

By no means I don't think math is not useful for a programmer. If anything, I regret I stupidly assumed I won't ever, ever, ever need complex math in my life so I didn't try to actually learn it. But still, here I am today, with not much knowledge in my programmer's math toolbelt. So I tried something different.

def getLargestPrimeFactor(number):

    # credits: http://primes.utm.edu/lists/small/100000.txt
    for line in reversed(open('primes.txt').readlines()):
        line = line.rstrip()
        line = ' '.join(line.split())
        if line:
            for prime in line.split(' '):
                if number % int(prime) == 0:
                    return prime

    return 1

I done a quick and dirty reverse parsing of a precomputed list of prime numbers and I had the answer pretty much instantly.

On the one side, I did some research, I came up with a solution. Was it an ortodox solution? It felt more like cheating. But in the end it worked.

I guess the best way would have been to do more research. Look into the prime number algorithms. Try to understand the math behind it. And yet, at the end of the day, I highly doubt it I'll ever need it outside of project Euler. I do mobile web developing stuff. And I reached my purpose of solving the problem.

If I consider the time spent, the probability of needing to solve this again in the future and the general use of prime factors for my line of work, I guess it wasn't cheating. But is surely feels like it...