How does the Sieve of Eratosthenes work?

Start with a list of integers 2..N. Take the first uncrossed number (2). Cross out all its multiples. Move to the next uncrossed number (3). Cross out its multiples. Repeat. What's left is all the primes. Far faster than trial-division for generating many primes.

Why is N capped at 10 million?

The sieve allocates one bit per integer; 10M bits = 1.25 MB, comfortably runs in browser memory. Beyond ~100M the page becomes unresponsive. For very large prime generation, use a server-side language with a segmented sieve.

How many primes are there below N?

Approximately N / ln(N). Below 100: 25 primes. Below 1,000: 168 primes. Below 1 million: 78,498 primes. The tool's output shows the exact count and density (primes per million).

sieve of eratosthenes · fast · local

Generate every prime up to N

Q: Is anything sent to a server?

No — the sieve runs in your browser.

Classic Sieve of Eratosthenes — fast, in-browser, up to 10 million. See density, sieve time, paginated output, and download every prime as text.

Prime Sieve

Count π(N)

168

primes ≤ N

Density

16.800%

π(N)/N

Largest

997

≤ N

Sieve time

0.2 ms

in-browser

input · bounds

Upper bound (N)

The sieve marks composites by their smallest prime factor — O(N log log N) time, O(N) memory.

output · primes (page 1/1)

page 1 / 1 · showing 168

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997

Quick Start

How the sieve works

Mark 2, 4, 6… as composite. Find the next unmarked (3) and mark 6, 9, 12. Continue until √N. What's left is every prime ≤ N.

01
Pick a bound
Any integer from 2 up to 10⁷.
Inputs are treated as UTF-8 throughout the pipeline and validated client-side as you type — nothing dispatches until the value is well-formed.
inpututf-8client-sidevalidated
N · text1000 · set
```
N = 1000
```
loaded · parsedclient-side
02
Sieve runs
Composites are flagged in a Uint8Array — sub-millisecond for N ≤ 10⁶.
Each toggle re-computes through a memoised hook, so flipping options never resets your input and the UI stays snappy on large inputs.
sieveoptionslivememoisedtoggles
ms · memoisedfast · live
```
1.2 ms
```
options set · memoisedlive
03
Browse the list
Paginated 200 at a time so the DOM stays responsive.
Randomness — where used — comes from crypto.getRandomValues, never Math.random. Heavy work sits in useMemo.
pagingcomputeinstantlocaldeterministic
page · instant1 · computed
```
2, 3, 5, 7, …
```
computed · instantinstant
04
Copy or download
Comma-list to clipboard, or one-per-line as .txt.
Copy writes through navigator.clipboard and downloads use a Blob — zero network traffic. Same input plus same options always yield the same bytes.
exportcopydownloadzero-networkreproducible
ok · copiedtxt · copied
```
Downloaded
```
shipped · ready to shipsuccess

Pro tips

Pro tips for everyday utilities

Reach for crypto.getRandomValues

Cryptographically random for IDs, tokens, salts. Math.random is for animation and games, not security.

Sort IDs lexicographically

UUID v4 has no time ordering. Use ULID or UUID v7 if you need sorted IDs.

Mock data with seeds

Faker-style libraries can be seeded so tests are reproducible. Embed the seed in the fixture file.

Reference cards beat memory

Cheatsheets for Vim, Git, Docker, Linux signals are faster than man pages when you’re mid-flow.

Browser APIs vary

Touch events, gamepads, and clipboard differ across vendors. Feature-detect before use.

Persist in the right place

localStorage for user preferences, sessionStorage for transient state, IndexedDB for structured data.

Use Cases

When to sieve primes

Algorithm courses, project Euler, number-theory homework.

Algorithm class

Visualise the sieve's runtime advantage over trial division. Random values come from crypto.getRandomValues — cryptographically secure for tokens, salts, and session IDs. Math.random is deterministic enough for animations but predictable enough to be a security bug.

CSPRNG-backed

Project Euler

Cache primes up to a bound for quick lookups. Pair with hashids, ULID, or UUID v7 when you need both random and sortable — useful for primary keys, public-facing IDs, and event log ordering without a sequence column.

reproducible

Number theory

Inspect π(N) growth and prime gaps directly. Output is deterministic given the same seed, so fixtures and tests stay reproducible across CI runs and contributor machines. Embed the seed in the fixture file for full replay.

snappy

Crypto warmup

Generate small primes for student RSA examples. Heavy work runs through useMemo so the UI stays snappy on large inputs. Same input + same options yields identical bytes — the kind of stability snapshot tests rely on.

feature-detected

Benchmark games

Time the sieve across browsers and hardware. Storage tools persist to the right backend: localStorage for user preferences, sessionStorage for transient state, IndexedDB for structured data. Pick the right shelf and quota worries disappear.

deterministic

Data sets

Download lists of primes for CSV imports and tests. Browser feature detection: clipboard, fullscreen, gamepad, and Web Bluetooth APIs gracefully fall back when unavailable. No surprise white screens on Safari or older Firefox.

production-ready

FAQ

Frequently asked questions

Why is 10⁷ the cap?

Allocating 10⁷ bytes and iterating fits in browser memory budgets. Larger sieves should stream from disk.

Why not segmented sieve?

For N ≤ 10⁷ the plain sieve is fast enough. Beyond that, segmenting is the right answer.

Does this use Wheel factorization?

No — clarity beats micro-optimisation here. The classic sieve is plenty fast in JavaScript.

Is the timing accurate?

We use performance.now() inside the same task. It excludes paint/render time but covers the actual sieve work.

Is anything sent to a server?

No — the sieve runs locally in your browser.

Suggest a tool

Something missing?

Tell us what you need. We ship the top requests every two weeks.

47 in queue·8 shipped this month

Request queued. Thanks!