DEV Community

Matt Ellen-Tsivintzeli
Matt Ellen-Tsivintzeli

Posted on

2

Optimising my sieve

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.

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay