Welcome to Dalton Firth's example Javascript prime number finder.

This programme finds all the prime numbers in any given range using a variant of a Sieve of Eratosthenes

Instead of checking each number in the range for primality by finding factors (factoring), which would be inefficient, the programme builds a map of all possible products in the given range. Any integer that is not in this list of products is therefore prime.

Click here for a graphical demo of the product mapping or enter an integer range here: -

FAQ:

  1. why am I doing this? As part of a project to benchmark Javascript performance for various maths-heavy algorithms - check out my knight's tour search algorithm too (work in progress).
  2. the search could take a while, depending on the power of your computer and efficiency of your web browser.
  3. Google Chrome was the quickest browser tested, searching the first 20 million integers to find the first million primes in ~1.5 seconds on a fast PC. Safari was a close second.
  4. Internet Explorer was the slowest, with Firefox and Opera not much better; the worst (IE) 10-times slower than Chrome
  5. How does Javascript compare to C? My highly-optimised C implementation runs 25 times faster than the fastest browser for small integers (<107), but Javascript is around 300 times slower for large integers (> 1012)
  6. looking for huge primes? Memory constraints and other inefficiencies limit the Javascript implementation. Many browsers struggle with ranges larger than ~20million and searches > UINT32 run at least 6 times slower.
  7. the algorithm scales far better in C, finding the first 38 billion primes in 2 hours (5 minutes) with a single 4GHz CPU 4-core 8-threaded CPU (but with a highly optimised routine not representative of the Javascript version)
  8. I used this useful site about prime numbers to verify the results from my implementation