Racket/Erastothenes

#lang racket

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

(require racket/format)

;; Skapar en vektor där indexet motsvarar talet.
;; Om (vector-ref v n) är #t, så är n ett primtal.
(define (make-sieve limit)
  ;; 1 SKAPA VEKTORN
  ;; Vi skapar en vektor med storleken (limit + 1). Eftersom index börjar på 0,
  ;; måste vektorn vara ett element större än 'limit' för att 'limit' ska få plats som sista index.
  ;; Vi antar från början att ALLA tal är primtal (#t), och sållar sedan bort de som inte är det.
  (define sieve (make-vector (add1 limit) #t))
  
  ;; 2 BASFALL (0 OCH 1)
  ;; 0 och 1 är aldrig primtal enligt definitionen (ett primtal måste vara större än 1).
  ;; Om användaren har angett en limit som inkluderar dessa, markerar vi dem direkt som #f (falskt).
  (when (>= limit 0) (vector-set! sieve 0 #f))
  (when (>= limit 1) (vector-set! sieve 1 #f))
  
  ;; 3 HUVUDLOOPEN (YTTRE)
  ;; Vi behöver bara gå upp till kvadratroten av limit (avrundat nedåt till heltal).
  ;; Varför? Om ett tal har en faktor som är större än kvadratroten, måste dess 
  ;; motsvarande partnerfaktor vara mindre än kvadratroten. Har vi redan rensat
  ;; alla mindre faktorer så har vi automatiskt tagit hand om de större!
  (for ((p (in-range 2 (add1 (integer-sqrt limit)))))
    
    ;; Om index 'p' fortfarande är #t, så har vi hittat ett primtal.
    (when (vector-ref sieve p)
      
      ;; 4 SÅLLNINGSLOOPEN (INRE)
      ;; Markera alla multiplar av p som falska (inte primtal).
      ;; Optimering: Vi startar direkt vid (* p p) istället för (* p 2).
      ;; Varför? Alla multiplar mindre än p*p (som 2p, 3p, 4p... upp till (p-1)p) 
      ;; har redan markerats som #f i tidigare varv av den yttre loopen.
      ;; Det tredje argumentet 'p' gör att loopen hoppar med p-steg i taget (p*p, p*p+p, p*p+2p, osv).
      (for ((multiple (in-range (* p p) (add1 limit) p)))
        (vector-set! sieve multiple #f)))) ; inte primtal
        
  ;; Returnera det färdiga sållet (vektorn) till anroparen
  sieve)


;; Returnerar en lista med alla primtal mellan start och stop
(define (primes-between start stop)
  ;; Kontrollera om intervallet är logiskt. Om start är större än stop finns det inga tal.
  (if (> start stop)
      '() ; Returnerar tomt om start > stop
      
      ;; Skapa sållet för hela intervallet upp till 'stop'.
      (let ((is-prime? (make-sieve stop)))
        
        ;; for/list samlar automatiskt ihop alla 'n' som matchar villkoret till en lista.
        ;; (max start 2) förhindrar att vi letar efter primtal under 2, då de inte finns.
        (for/list ((n (in-range (max start 2) (add1 stop)))
                   #:when (vector-ref is-prime? n)) ; Villkor: Endast om index n är #t i sållet
          n))))


;; Hjälpmakro för att tajma hur lång tid operationen tog
(define-syntax-rule (timeit expr)
  ;; Spara starttiden i millisekunder innan uttrycket körs
  (let ((start (current-inexact-milliseconds)))
    ;; Kör uttrycket 'expr' (t.ex. vår funktion) och spara resultatet i 'result'
    (let ((result expr))
      ;; Skriv ut tidsskillnaden med snygg lokal formatering
      (printf "Tid: ~a ms\n" (~r (- (current-inexact-milliseconds) start)
                                #:group-sep   " "     ; tusentalsavskiljare (blanksteg)
                                #:decimal-sep ","     ; decimalsavskiljare (komma)
                                #:precision     2))   ; avrunda till 2 decimaler
      result)))  ; Returnera svaret från expr så att programmet kan använda det


;; Testkörning
(timeit (primes-between 10000000 10000500))