Racket/Erastothenes

1. 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))