Algorithm
I think you've gotten distracted by focusing on the wrong aspect of the problem.
The challenge asks for the largest prime factor of n = 600851475143. There are three approaches you might consider in tackling this challenge:
Construct the list of all relevant prime numbers, then take the largest one.
How high do we need consider? The largest candidate would be \$\left\lceil\sqrt{n}\right\rceil\$.
What algorithm could we use? A good method to build a list of many prime numbers is the Sieve of Eratosthenes. That would require \$\left\lceil\sqrt{n}\right\rceil\$ bits of memory, or 70 GiB. Even if you had a machine with that much memory, just initializing that much memory to zero would be too slow to be reasonable as a Project Euler solution.
Any other algorithm for building a list of primes would only be worse.
You didn't choose Door #1. Good for you!
Test the largest candidate factors first.
Where would you start? The largest candidate would be \$\left\lceil\sqrt{n}\right\rceil\$. You can test odd candidates in descending order, stopping as soon as you find an answer that is prime.
How do you guarantee that the answer is prime? You have to check for primality. We've already ruled out the Sieve of Eratosthenes above, so you would have to use trial division or a fancier primality-testing algorithm.
How long would we expect this to take? \$\left\lceil\sqrt{n}\right\rceil\$ is 775147. We would have 387573 possible odd factors to test. There's no telling where we'll find numbers that are actually factors of \$n\$. Once we find a factor, we still have to verify whether it's prime.
Food for thought: what would you do if \$n\$ were even?
You didn't choose Door #2, even though some other users have advocated it. Good for you!
Test the smallest candidate factors first.
Suppose that I asked you to find the largest prime factor of 10241. How would you go about it? Would you start at \$\left\lceil\sqrt{10241}\ \right\rceil\$, trying 103, 101, 99, 97, 95, ...?
Chances are you would prefer to do it this way, and you could do it with just pencil and paper. (It's also easy to implement as one function.)
- 10241 / 2 ... no.
- 10241 / 3 ... no.
- 10241 / 5 ... no.
- 10241 / 7 = 1463
- 1463 / 7 = 209
- 209 / 7 ... no.
- 209 / 9 ... no.
- 209 / 11 ... no.
- 209 / 13 ... no.
- 209 / 15 ... no.
- 209 / 17 = no.
- 209 / 19 = 11
- 11 / 19 ... that's silly, there are no more factors to test!
As you can see, the big win comes when you find that 10241 is divisible by 7 — you immediately reduce the search space by a factor of 7. In just a few iterations, you've reduced the problem size from 10241 down to 209 — a much more manageable number.
Bonus question: in the example above, do we still need to test 11 for primality? Why or why not?
As it turns out, strategy 3 also works well for Project Euler Problem 3. In general, strategy 3 is a better bet than strategy 2, since prime numbers tend to be more densely clustered closer to 0.
You've chosen an algorithm that is similar to strategy 3, which is good. However, it isn't the same solution. Your computeFactors() function very closely mimics the algorithm illustrated for strategy 3, but with a subtle and crucial difference. Can you spot it?
- 145.5k
- 22
- 190
- 479