; numbers with 3 divisors
(define (isqrt n)
(if (not (and (positive? n) (integer? n)))
(error 'isqrt "must be positive integer")
(let loop ((x n))
(let ((y (quotient (+ x (quotient n x)) 2)))
(if (< y x) (loop y) x)))))
(define (primes n) ; list of primes not exceeding n
(let* ((len (quotient (- n 1) 2)) (bits (make-vector len #t)))
(let loop ((i 0) (p 3) (ps (list 2)))
(cond ((< n (* p p))
(do ((i i (+ i 1)) (p p (+ p 2))
(ps ps (if (vector-ref bits i) (cons p ps) ps)))
((= i len) (reverse ps))))
((vector-ref bits i)
(do ((j (+ (* 2 i i) (* 6 i) 3) (+ j p)))
((<= len j) (loop (+ i 1) (+ p 2) (cons p ps)))
(vector-set! bits j #f)))
(else (loop (+ i 1) (+ p 2) ps))))))
(define (f n) (length (primes (isqrt n))))
(display (f 1000000000)) (newline)
OyBudW1iZXJzIHdpdGggMyBkaXZpc29ycwoKKGRlZmluZSAoaXNxcnQgbikKICAoaWYgKG5vdCAoYW5kIChwb3NpdGl2ZT8gbikgKGludGVnZXI/IG4pKSkKICAgICAgKGVycm9yICdpc3FydCAibXVzdCBiZSBwb3NpdGl2ZSBpbnRlZ2VyIikKICAgICAgKGxldCBsb29wICgoeCBuKSkKICAgICAgICAobGV0ICgoeSAocXVvdGllbnQgKCsgeCAocXVvdGllbnQgbiB4KSkgMikpKQogICAgICAgICAgKGlmICg8IHkgeCkgKGxvb3AgeSkgeCkpKSkpCgooZGVmaW5lIChwcmltZXMgbikgOyBsaXN0IG9mIHByaW1lcyBub3QgZXhjZWVkaW5nIG4KICAobGV0KiAoKGxlbiAocXVvdGllbnQgKC0gbiAxKSAyKSkgKGJpdHMgKG1ha2UtdmVjdG9yIGxlbiAjdCkpKQogICAgKGxldCBsb29wICgoaSAwKSAocCAzKSAocHMgKGxpc3QgMikpKQogICAgICAoY29uZCAoKDwgbiAoKiBwIHApKQogICAgICAgICAgICAgIChkbyAoKGkgaSAoKyBpIDEpKSAocCBwICgrIHAgMikpCiAgICAgICAgICAgICAgICAgICAocHMgcHMgKGlmICh2ZWN0b3ItcmVmIGJpdHMgaSkgKGNvbnMgcCBwcykgcHMpKSkKICAgICAgICAgICAgICAgICAgKCg9IGkgbGVuKSAocmV2ZXJzZSBwcykpKSkKICAgICAgICAgICAgKCh2ZWN0b3ItcmVmIGJpdHMgaSkKICAgICAgICAgICAgICAoZG8gKChqICgrICgqIDIgaSBpKSAoKiA2IGkpIDMpICgrIGogcCkpKQogICAgICAgICAgICAgICAgICAoKDw9IGxlbiBqKSAobG9vcCAoKyBpIDEpICgrIHAgMikgKGNvbnMgcCBwcykpKQogICAgICAgICAgICAgICAgKHZlY3Rvci1zZXQhIGJpdHMgaiAjZikpKQogICAgICAgICAgICAoZWxzZSAobG9vcCAoKyBpIDEpICgrIHAgMikgcHMpKSkpKSkKCihkZWZpbmUgKGYgbikgKGxlbmd0aCAocHJpbWVzIChpc3FydCBuKSkpKQoKKGRpc3BsYXkgKGYgMTAwMDAwMDAwMCkpIChuZXdsaW5lKQ==