; 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==