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.

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.

Results go here

Number of primes less than N (from

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