Racket/Erastothenes

#lang racket

;;;;;
;; Erastothenes såll implementerad i Racket
;; Täpp-Anders Sikvall 2026-04-03 anders@sikvall.se
;;;;;

(define (primes-between start stop)
  (cond
    [(> start stop) '()]
    [else
     ; Skapa en bool-vektor för intervallet [0..stop]
     (define sieve (make-vector (+ stop 1) #t))
     
     ; 0 och 1 är inte primtal
     (vector-set! sieve 0 #f)
     (vector-set! sieve 1 #f)
     
     ; Såll: markera multiplar
     ; Går från 2 till (roten ur stop) +1
     ; inre vektorn går från i^2 till stop med steglängden i
     ; och markerar multiplarna av i genom hela vektorfältet
     (for ([i (in-range 2 (add1 (integer-sqrt stop)))])
       (when (vector-ref sieve i)
         (for ([j (in-range (* i i) (add1 stop) i)])
           (vector-set! sieve j #f))))
     
     ; Samla ihop primtal i intervallet [start, stop]
     (for/list ([i (in-range (max start 2) (add1 stop))]
                #:when (vector-ref sieve i))
       i)]))

; Exempel på användning:
(primes-between 100000 200000)   ; funkar snabbt även för stora tal