F primes_up_to_limit(Int limit)
   [Int] r
   I limit >= 2
      r.append(2)

   V isprime = [1B] * ((limit - 1) I/ 2)
   V sieveend = Int(sqrt(limit))
   L(i) 0 .< isprime.len
      I isprime[i]
         Int p = i * 2 + 3
         r.append(p)
         I i <= sieveend
            L(j) ((p * p - 3) >> 1 .< isprime.len).step(p)
               isprime[j] = 0B
   R r

V p = primes_up_to_limit(Int(sqrt(1'000'000'000)))

F phi(x, =a)
   F phi_cached(x, a)
      [(Int, Int) = Int] :cache
      I (x, a) C :cache
         R :cache[(x, a)]
      V r = phi(x, a)
      :cache[(x, a)] = r
      R r

   V res = 0
   L
      I a == 0 | x == 0
         R x + res

      a--
      res -= phi_cached(x I/ :p[a], a)

F legpi(n)
   I n < 2
      R 0

   V a = legpi(Int(sqrt(n)))
   R phi(n, a) + a - 1

L(e) 0.<10
   print(‘10^’e‘ ’legpi(10 ^ e))