Sieve of Eratosthenes

// Sieve of Eratosthenes — visualize prime discovery on a grid of 2..N+1.
// State per cell: 0 unknown, 1 prime (confirmed), 2 composite (marked red),
// 3 the current sieving prime (highlighted).
const N = 625;          // we visualize integers 2..N+1 inclusive (624 cells)
const COLS = 25;        // 25 x 25 grid of integers
const ROWS = 25;
let state;              // Uint8Array(COLS*ROWS)
let primes;             // ordered list of primes discovered
let primeCenters;       // {x,y} cell centers, for arcs
let cur;                // index in 0..COLS*ROWS-1 of the prime we're sieving
let mark;               // next composite multiple (integer 2..N+1) to mark
let step;               // increment for marking (== current prime)
let phase;              // "sieve" or "done"
let pulse;              // time accumulator for done-state pulse
let W = 0, H = 0;
let gx = 0, gy = 0;     // grid origin (top-left of cell grid in canvas px)
let cell = 0;           // cell side in px
let stepsPerFrame = 1;  // mark this many composites per tick

function valAt(idx) { return idx + 2; }            // cell index -> integer
function idxOf(val) { return val - 2; }            // integer -> cell index
function colOf(idx) { return idx % COLS; }
function rowOf(idx) { return (idx / COLS) | 0; }

function layout(width, height) {
  W = width; H = height;
  // Reserve top HUD strip (~58px). Grid fills the rest as a centered square.
  const top = 58;
  const avail = Math.max(40, Math.min(W - 24, H - top - 12));
  cell = Math.floor(avail / COLS);
  if (cell < 8) cell = 8;
  const gridSide = cell * COLS;
  gx = Math.floor((W - gridSide) / 2);
  gy = top + Math.floor((H - top - gridSide) / 2);
  // Recompute prime centers for arcs.
  for (let i = 0; i < primes.length; i++) {
    const idx = idxOf(primes[i]);
    primeCenters[i] = {
      x: gx + colOf(idx) * cell + cell / 2,
      y: gy + rowOf(idx) * cell + cell / 2,
    };
  }
}

function init({ width, height }) {
  state = new Uint8Array(COLS * ROWS);
  primes = [];
  primeCenters = [];
  cur = 0;          // start at 2
  state[cur] = 3;
  primes.push(2);
  primeCenters.push({ x: 0, y: 0 });
  step = 2;
  mark = 4;         // first composite to mark for prime 2
  phase = "sieve";
  pulse = 0;
  stepsPerFrame = 1;
  layout(width, height);
}

function advanceToNextPrime() {
  // Confirm the previous prime, then walk forward to first unknown cell.
  state[cur] = 1;
  let next = cur + 1;
  while (next < COLS * ROWS && state[next] !== 0) next++;
  if (next >= COLS * ROWS) {
    phase = "done";
    return;
  }
  cur = next;
  state[cur] = 3;
  const p = valAt(cur);
  primes.push(p);
  primeCenters.push({
    x: gx + colOf(cur) * cell + cell / 2,
    y: gy + rowOf(cur) * cell + cell / 2,
  });
  step = p;
  mark = p * p;     // optimization: smaller multiples already crossed off
  if (mark > N + 1) {
    // No composites left to mark for this prime; immediately advance again.
    advanceToNextPrime();
  }
}

function tick({ ctx, width, height, dt }) {
  if (width !== W || height !== H) layout(width, height);

  // Sieve work: a few steps per frame, accelerating gently over time.
  if (phase === "sieve") {
    stepsPerFrame = Math.min(8, 1 + Math.floor(primes.length / 12));
    for (let s = 0; s < stepsPerFrame && phase === "sieve"; s++) {
      if (mark > N + 1) {
        advanceToNextPrime();
      } else {
        const mi = idxOf(mark);
        if (state[mi] === 0) state[mi] = 2;
        mark += step;
      }
    }
  } else {
    pulse += dt;
  }

  // Background.
  ctx.fillStyle = "#0a0d14";
  ctx.fillRect(0, 0, W, H);

  drawGrid(ctx);
  drawArcs(ctx);
  drawHUD(ctx);
}

function drawGrid(ctx) {
  const fontPx = Math.max(8, Math.floor(cell * 0.42));
  ctx.font = `${fontPx}px monospace`;
  ctx.textAlign = "center";
  ctx.textBaseline = "middle";

  for (let i = 0; i < COLS * ROWS; i++) {
    const v = valAt(i);
    if (v > N + 1) break;
    const x = gx + colOf(i) * cell;
    const y = gy + rowOf(i) * cell;
    const s = state[i];

    let fill, stroke, text;
    if (s === 2) {
      fill = "#3a1418"; stroke = "#5a1f25"; text = "#ff6b6b";
    } else if (s === 1) {
      fill = "#10301c"; stroke = "#1f5a36"; text = "#7be0a6";
    } else if (s === 3) {
      // Cursor cell: bright yellow.
      fill = "#3a3210"; stroke = "#ffd166"; text = "#ffe9a8";
    } else {
      fill = "#121724"; stroke = "#1d2434"; text = "#cfd6e4";
    }
    ctx.fillStyle = fill;
    ctx.fillRect(x + 1, y + 1, cell - 2, cell - 2);
    ctx.strokeStyle = stroke;
    ctx.lineWidth = 1;
    ctx.strokeRect(x + 0.5, y + 0.5, cell - 1, cell - 1);

    // Active mark cursor: a small ring on the cell currently being struck.
    if (phase === "sieve" && mark <= N + 1 && i === idxOf(mark)) {
      ctx.strokeStyle = "rgba(255,107,107,0.9)";
      ctx.lineWidth = 2;
      ctx.beginPath();
      ctx.arc(x + cell / 2, y + cell / 2, cell * 0.42, 0, Math.PI * 2);
      ctx.stroke();
      ctx.lineWidth = 1;
    }

    ctx.fillStyle = text;
    ctx.fillText(String(v), x + cell / 2, y + cell / 2 + 1);

    // Cross-out for marked composites.
    if (s === 2) {
      ctx.strokeStyle = "rgba(255,107,107,0.55)";
      ctx.lineWidth = 1;
      ctx.beginPath();
      ctx.moveTo(x + 3, y + 3);
      ctx.lineTo(x + cell - 3, y + cell - 3);
      ctx.stroke();
    }
  }
}

function drawArcs(ctx) {
  if (primeCenters.length < 2) return;
  // Faint connecting arcs between consecutive primes. Curve sign alternates
  // so the trail doesn't all bulge the same way.
  ctx.lineWidth = 1;
  ctx.strokeStyle = "rgba(123,224,166,0.18)";
  ctx.beginPath();
  for (let i = 1; i < primeCenters.length; i++) {
    const a = primeCenters[i - 1], b = primeCenters[i];
    const mx = (a.x + b.x) / 2, my = (a.y + b.y) / 2;
    const dx = b.x - a.x, dy = b.y - a.y;
    const len = Math.hypot(dx, dy) || 1;
    const nx = -dy / len, ny = dx / len;
    const bulge = (i % 2 === 0 ? 1 : -1) * Math.min(28, len * 0.18);
    const cx = mx + nx * bulge, cy = my + ny * bulge;
    ctx.moveTo(a.x, a.y);
    ctx.quadraticCurveTo(cx, cy, b.x, b.y);
  }
  ctx.stroke();
}

function drawHUD(ctx) {
  const top = 58;
  ctx.fillStyle = "rgba(0,0,0,0.55)";
  ctx.fillRect(0, 0, W, top);

  ctx.fillStyle = "#fff";
  ctx.font = "13px monospace";
  ctx.textAlign = "left";
  ctx.textBaseline = "alphabetic";
  ctx.fillText(`Sieve of Eratosthenes   N = ${N + 1}`, 12, 20);

  const confirmed = phase === "done" ? primes.length : Math.max(0, primes.length - 1);
  const piApprox = (N + 1) / Math.log(N + 1);
  ctx.fillText(`primes found : ${confirmed}`, 12, 38);
  ctx.fillText(`π(N) ≈ N/ln N = ${piApprox.toFixed(1)}`, 200, 38);

  if (phase === "sieve") {
    const p = primes[primes.length - 1];
    ctx.fillStyle = "#ffd166";
    ctx.fillText(`sieving multiples of ${p}`, 12, 54);
  } else {
    const err = primes.length - piApprox;
    const sign = err >= 0 ? "+" : "";
    // Pulse the done banner.
    const a = 0.6 + 0.4 * Math.sin(pulse * 3);
    ctx.fillStyle = `rgba(123,224,166,${a.toFixed(3)})`;
    ctx.fillText(
      `done · π(${N + 1}) = ${primes.length}   (approx err ${sign}${err.toFixed(1)})`,
      12,
      54,
    );
  }
}