Sieve of Eratosthenes

List the prime numbers up to

Enter a number and hit return. A JavaScript program will run. Be patient! Start with a low limit, to check it is working. If you ask for more than 30 million primes, there may be a delay in the web page responding. I think that this may be partly due to the sluggishness of browsers, sometimes, and partly due to your PC running out of memory.

Results go here

Number of primes less than N (from https://en.wikipedia.org/wiki/Prime-counting_function)

N π(N)
10 4
100 25
1000 168
10,000 1,229
100,000 9,592
1,000,000 78,498
10,000,000 664,579
100,000,000 5,761,455

Notes

The algorithm I am using is crude. For one thing, it uses a lot of memory. A simple improvement to speed, which I have incorporated, is to consider only odd numbers. A further, related improvement would be to only store data for odd numbers, which would halve the memory requirement; but I have not made this (fairly simple) change to the code. There are other possible improvements to the algorithm, such as eliminating the need for testing numbers already known not to be prime, as the algorithm progresses. To view the JavaScript, ask your browser to show the source code for this page, and click on the link to the <SCRIPT> file.

Its interesting to look at the speed of JS. You can see, from the above results that the sieve is testing of the order of ten million numbers a second (but that depends on the speed of your PC of course). I found some notes on a similar sieve that I wrote back in February 1988, some 30 years ago. Here are the benchmarks for that test, for testing numbers up to 8191.

The fastest of those is managing just 3200 tests per second, so it is some 3000 times slower than JS running on my laptop in Windows 10. I suppose you would expect that sort of increase in performance, as clock speeds are, say, 1000 times faster and bus-bandwidth 8 times greater, giving a potential 8,000 times improvement factor.

This page created on 02-Aug-2019. Latest modifications: 28-Aug-2021