typestar

prime_sieve.wat in WebAssembly

The Sieve of Eratosthenes in linear memory: 25 primes at or below 100.

;; Sieve of Eratosthenes in one memory page: count the primes to 100.
(module
  (memory 1)

  ;; Mark every composite: for each prime p, cross off p*p, p*p+p, ...
  (func $sieve (param $limit i32)
    (local $p i32)
    (local $m i32)
    (local.set $p (i32.const 2))
    (block $done
      (loop $next_p
        (br_if $done
          (i32.gt_s (i32.mul (local.get $p) (local.get $p))
                    (local.get $limit)))
        (if (i32.eqz (i32.load8_u (local.get $p)))
          (then
            (local.set $m (i32.mul (local.get $p) (local.get $p)))
            (block $marked
              (loop $mark
                (br_if $marked
                  (i32.gt_s (local.get $m) (local.get $limit)))
                (i32.store8 (local.get $m) (i32.const 1))
                (local.set $m (i32.add (local.get $m) (local.get $p)))
                (br $mark)))))
        (local.set $p (i32.add (local.get $p) (i32.const 1)))
        (br $next_p))))

  ;; Anything still zero after the sieve is prime.
  (func $count_primes (export "count_primes") (param $limit i32)
        (result i32)
    (local $n i32)
    (local $count i32)
    (call $sieve (local.get $limit))
    (local.set $n (i32.const 2))
    (block $done
      (loop $scan
        (br_if $done (i32.gt_s (local.get $n) (local.get $limit)))
        (if (i32.eqz (i32.load8_u (local.get $n)))
          (then
            (local.set $count
              (i32.add (local.get $count) (i32.const 1)))))
        (local.set $n (i32.add (local.get $n) (i32.const 1)))
        (br $scan)))
    (local.get $count))

  ;; There are 25 primes at or below 100.
  (func (export "main") (result i32)
    (call $count_primes (i32.const 100))))

How it works

  1. $sieve crosses off composites, each prime striding from p*p.
  2. Nested block/loop pairs make the two-level for loop.
  3. count_primes rescans memory; main answers 25 for a limit of 100.

Keywords and builtins used here

The run, in numbers

Lines
48
Characters to type
1355
Tokens
314
Three-star pace
60 tpm

At the three-star pace of 60 tokens a minute, this run takes about 314 seconds.

Type this snippet

Step 1 of 3 in Encore, step 26 of 28 in Language basics.

← Previous Next →