Last time we hit a limit on the largest prime that could be found in a reasonable amount of time. On my laptop that was around the 10000th.
So, how can the algorithm be optimised?
I found two ways that have made the algorithm 100 times faster.
Firstly, there was the multiplier that allowed us to search for the Nth prime. Originally I set it to 20 through some guestimating, but after looking in more detail, and limiting N to 1,000,000, I found that the smallest multiplier that covers the first 1,000,000 primes is 16, as the one millionth prime is between 15,000,000 and 16,000,000.
Setting a smaller multiplier means that the initial array is a lot smaller (four times smaller), so iterating through it takes less time.
The second optimistation is where to start looking for the next prime. In the original I start at the last prime + 1, however, some simple reasoning will show that if you have eliminated all numbers properly divisble by other numbers upto n then the next non-prime will be at or after n×n. So the steps are a lot bigger. This is by far the biggest optimisation.
Have a play with this codepen. I've limited it to the first 1,000,000 primes, but feel free to take the algorithm and remove the limiter to see how high you can go.
Fun fact: the 619th prime is 4567.
Top comments (0)