#lang racket/base

;;; This benchmark is adapted from the version from Grift
;;; Original source: https://github.com/Gradual-Typing/benchmarks
;;; It was originally defined as two modules, but was modified to combine it into a single module

;; Simple streams library.
;; For building and using infinite lists.

(define stream-first car)

(define (stream-rest st) ((cdr st)))

;;--------------------------------------------------------------------------------------------------

(define (make-stream hd thunk)
  (cons hd thunk))

;; Destruct a stream into its first value and the new stream produced
;; by de-thunking the tail
(define (stream-unfold st)
  (cons (stream-first st) (stream-rest st)))

;; [stream-get st i] Get the [i]-th element from the stream [st]
(define (stream-get st i)
  (cond
    [(= i 0) (stream-first st)]
    [else (stream-get (stream-rest st) (sub1 i))]))

;;--------------------------------------------------------------------------------------------------

;; `count-from n` Build a stream of integers starting from `n` and iteratively adding 1

(define (count-from n)
  (make-stream n (lambda () (count-from (add1 n)))))

;; `sift n st` Filter all elements in `st` that are equal to `n`.
;; Return a new stream.
(define (sift n st)
  (define hd (stream-first st))
  (cond
    [(eq? 0 (modulo hd n))
     (sift n (stream-rest st))]
    [else
     (make-stream hd (lambda () (sift n (stream-rest st))))]))

;; `sieve st` Sieve of Eratosthenes
(define (sieve st)
  (define hd (stream-first st))
  (make-stream hd (lambda () (sieve (sift hd (stream-rest st))))))

;; stream of prime numbers
(define primes (sieve (count-from 2)))

(define (main)
  (let ([N-1 (read)])
    (display (stream-get primes N-1))
    (newline)))

(time (main))
