UIREADY.dev
Prime Check / SieveLoading saved progress…

Prime Check / Sieve

A prime number is an integer greater than 1 whose only whole-number divisors are 1 and itself — 2, 3, 5, 7, 11 and so on. You will build two functions on one object, primeSieve = { isPrime, sieve }: isPrime(n) decides whether a single number is prime, and sieve(n) returns every prime up to n using the Sieve of Eratosthenes, an ancient method that finds all the primes in a range by repeatedly crossing out multiples. See prime number for background.

Signature

primeSieve.isPrime(n)  // integer -> boolean: is n prime?
primeSieve.sieve(n)    // integer -> number[]: all primes <= n, ascending

Examples

primeSieve.isPrime(2);    // true
primeSieve.isPrime(1);    // false  (1 is not prime)
primeSieve.isPrime(97);   // true
primeSieve.isPrime(100);  // false  (100 = 2 * 2 * 5 * 5)
primeSieve.sieve(10);  // [2, 3, 5, 7]
primeSieve.sieve(30);  // [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
primeSieve.sieve(1);   // []   (there are no primes below 2)

Notes

  • Nothing below 2 is prime — isPrime returns false for 0, for 1, and for every negative number.
  • 2 is the only even prime — every other even number is divisible by 2, so it is composite.
  • Only test up to the square root — if n has a divisor larger than its square root, it also has a matching one that is smaller, so you never need to look past the square root of n.
  • The sieve is inclusive — sieve(n) includes n itself when n is prime (so sieve(7) ends with 7), and returns [] for any n below 2.
  • No libraries — build both functions yourself; no math libraries.

FAQ

Why only test divisors up to the square root of n?
If n splits into a times b, one of the two factors is at most the square root of n. So if nothing from 2 up to the square root divides n, no larger number can either, because its partner factor would be smaller and you would already have found it. That shrinks isPrime from about n divisions to about the square root of n.
Why does the sieve start crossing out at p times p instead of 2 times p?
Every smaller multiple of p, from 2p up to (p minus 1) times p, has a smaller prime factor and was already crossed out on an earlier pass. Starting at p squared skips that repeated work; it is why the whole sieve runs in roughly n log log n time.
When should you use isPrime versus the sieve?
Use isPrime to test one number or a handful. Use the sieve when you need every prime up to a bound: calling isPrime on each of 2..n repeats work, while the sieve crosses out multiples once and lands in about n log log n total.
Loading editor…