The problem for this one sounds simple enough…

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? From https://projecteuler.net/problem=3.

So I started out first by calculating all of the prime numbers up to half of the given value. I then filtered them out to only the ones that match factors of that value and took the largest. This worked great for the initial test data I’d chosen but when I jumped up to using the target value of 600851475143 and I assumed it had frozen. Nope, the algorithm was just so slow I could have been there some time.

After a little analysis, I realised that I had a couple of problems…

• Problem 1: calculating factors is quicker than primes but I’d chosen to calculate primes and filter on factors rather than the other way round.
• Problem 2: I’d used the Sieve of Eratosthenes to generate primes which may be simple to implement and fast for small primes but its quite slow for larger primes.

Problem 1 was solved easily enough by reversing the order of the calculations but I needed to do a little googling to find a better prime checker. The wikipedia article on primality testing discusses various approaches but first I tried trial division with the optimization of only testing divisors up to √n. This made the algorithm fast enough to reach the target value so I left it like that.