π(x) — Prime Counting Function Calculator

A fast, practical tool for computing π(x) — the number of primes less than or equal to x — for any x up to 2 × 10¹².

Try it in your browser →

How It Works

The tool uses a precomputed prefix-sum table with a wheel-30 segmented sieve for gap-filling:

1. Build phase (one-time): Sieves the entire range block by block, storing cumulative π values at every 30,000,000-number interval. The table for 2 × 10¹² is only 521 KB.

2. Query phase (instant): For any π(x), looks up the nearest checkpoint (O(1)), then runs a tiny wheel-30 sieve over at most 30M numbers to count the remainder. Typical query time: < 1 ms.

3. Extend phase (incremental): To push the table further, only the new range is sieved. Previous work is never redone.

Web Version (WASM)

The browser version loads the 521 KB table and runs the sieve in WebAssembly for near-native speed. No server needed — everything runs client-side.

Quick Start

Use the Web Version

Visit https://psaraj12.github.io/prime-pi/ — no installation needed.

Build from Source (C++ CLI)

# Compile
g++ -O3 -march=native -fopenmp -std=c++17 -o prime_pi prime_pi_fine.cpp

# Build table to 10^12 (one-time, ~8 minutes on 12 threads)
./prime_pi build 1000000000000 12 pi.dat

# Query — instant
./prime_pi query 1000000000000 pi.dat
# π(1000000000000) = 37607912018
# Query time: 42.3 µs

# Extend to 2×10^12 (only sieves the new range)
./prime_pi extend 2000000000000 12 pi.dat

# Table info
./prime_pi info pi.dat

Build the WASM Module

# Install Emscripten: https://emscripten.org/docs/getting_started/downloads.html
source emsdk_env.sh

# Build WASM
chmod +x build_wasm.sh
./build_wasm.sh

# Serve locally
cd docs && python3 -m http.server 8080
# Open http://localhost:8080

Performance

Benchmarked on ASUS Vivobook, AMD Ryzen 5, 12 threads:

Operation	Range	Time	Rate
Build	π(10¹²)	~8 min	~1,900 M/s
Extend	10¹² → 2×10¹²	~8 min	~1,900 M/s
Query	Any x ≤ 2×10¹²	< 1 ms	—

Known Values (Verification)

x	π(x)
10⁶	78,498
10⁹	50,847,534
10¹⁰	455,052,511
10¹¹	4,118,054,813
10¹²	37,607,912,018

Architecture

┌─────────────────────────────────────────────────┐
│  Prefix-Sum Table (pi.dat, 521 KB)              │
│  checkpoint[i] = π(i × 30,000,000 - 1)         │
│  66,667 entries covering [0, 2×10¹²]            │
└──────────────┬──────────────────────────────────┘
               │
    Query π(x) │
               ▼
  ┌──────────────────────┐
  │ 1. Lookup checkpoint │  O(1) — array index
  │    ci = x / 30M      │
  │    base = table[ci-1] │
  └──────────┬───────────┘
             │
             ▼
  ┌──────────────────────┐
  │ 2. Sieve gap         │  Wheel-30, ≤ 30M numbers
  │    [ci×30M, x]       │  ~0.1–1 ms
  │    count = popcount   │
  └──────────┬───────────┘
             │
             ▼
  ┌──────────────────────┐
  │ 3. Return            │
  │    π(x) = base+count │
  └──────────────────────┘

Wheel-30 Sieve

Only stores numbers coprime to 30 (not divisible by 2, 3, or 5). This means 8 bits per 30 numbers instead of 15 bits (odd-only), reducing memory by 47% and sieve work proportionally. Primes 2, 3, 5 are counted separately.

Incremental Extend

The extend command loads an existing table, sieves only the new range, and appends the new prefix-sum entries. This means you can build the table in stages:

./prime_pi build  1000000000000 12 pi.dat   # 10^12 — 8 min
./prime_pi extend 2000000000000 12 pi.dat   # extend — 8 min more
./prime_pi extend 3000000000000 12 pi.dat   # extend — 8 min more

Each run only does new work. The table file grows by ~260 KB per 10¹².

File Structure

prime-pi/
├── prime_pi_fine.cpp       # C++ source (CLI: build/extend/query/info)
├── pi_query_wasm.cpp       # C++ source (WASM query module)
├── build_wasm.sh           # Emscripten build script
├── docs/                   # GitHub Pages site
│   ├── index.html          # Web UI
│   ├── pi.dat              # Precomputed table (521 KB)
│   ├── pi_query.js         # WASM glue (generated by emcc)
│   └── pi_query.wasm       # WASM binary (generated by emcc)
└── README.md

Deploy to GitHub Pages

1. Push to GitHub
2. Go to Settings → Pages → Source → Deploy from branch → main → /docs
3. Your calculator is live at https://<username>.github.io/prime-pi/

License

MIT