Number of Primes

A proposed solution to exercise 3.3 from Stepanov and Rose’s From Mathematics to Generic Programming. The exercise asks us to graph the number of primes less than n using an analytic approximation.

• The black line represents the actual number of primes less than x.
• The dashed red line represents an approximating function π = (x) => x / Math.log(x).
• Orange dots represent the measured time taken to sift a sieve for the given input size. Their scale is necessarily different from the one used for displaying the counts of primes; it reflects relative differences in the milliseconds taken to run the Sieve of Eratosthenes algorithm.

A Web Worker performs each test of increasing input size and reports back to the main thread with the number of primes found that are less than the input. Only one test actually needs to be run in order to graph the prime-counting function; however, by running each test separately in a WebWorker (each with a successively larger different input size), one can perform a complexity analysis of the various implementations of the Sieve of Eratosthenes.

Using Web Workers in this example also helps us avoid locking up the main user interface thread while the algorithm is executing.