(do ;;; Legendre prime counting function - translation of EasyLang

    ; generate and return a table containing the primes up to sieve-size
    (fn prime-sieve [sieve-size]
        (var sieve {})
        (tset sieve 1 false)
        (for [s-pos 2 sieve-size] (tset sieve s-pos true))
        (for [s-pos 2 (math.floor (math.sqrt sieve-size))]
             (when (. sieve s-pos)
                   (for [p (* s-pos s-pos) sieve-size s-pos] (tset sieve p false))
             )
        )
        sieve
    )

    ; construct a sieve of primes up to the maximum we will need
    (var ps-root-1e9 (prime-sieve (math.sqrt 1e9)))

    ; returns a table of primes extracted from a prime sieve
    (fn primes-up-to [n sieve]
        (local result {})
        (for [s-pos 1 n]
             (when (. sieve s-pos) (table.insert result s-pos))
        )
        result
    )

    (fn legendre-pi [n]
        (if (< n 2) 0
            (= n 2) 1
        ;else
            (do (local root-n      (math.floor (math.sqrt n)))
                (local primes      (primes-up-to root-n ps-root-1e9))
                (local prime-count (length primes))

                (fn phi [x a-in]
                    (var (a sum found-1) (values a-in 0 false))
                    (while (and (> a 1) (not found-1))
                           (local pa (. primes a))
                           (if (<= x pa)
                               (set found-1 true)
                           ;else
                               (do (set a   (- a 1))
                                   (set sum (+ sum (phi (// x pa) a)))
                               )
                           )
                    )
                    (if found-1
                        1
                    ;else
                        (- x (// x 2 ) sum)
                    )
                )

                (- (+ (phi n prime-count) prime-count) 1)
            )
        )
    )

    (for [i 0 9]
         (print (string.format "10^%d  %d" i (legendre-pi (^ 10 i))))
    )
)