Racket/Erastothenes

#lang racket

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


;; Skapar en vektor där indexet motsvarar talet.
;; Om (vector-ref v n) är #t, så är n ett primtal.

(define (make-sieve limit)
  (define sieve (make-vector (add1 limit) #t))
  
  ;; 0 och 1 är aldrig primtal
  ;; Primtal är tal som är större än 1 och endast jämt delbara med
  ;; sig själv eller 1. Så börja med att markera 0 och 1 som icke-prim.
  (when (>= limit 0) (vector-set! sieve 0 #f))
  (when (>= limit 1) (vector-set! sieve 1 #f))
  
  ;; Vi behöver bara gå upp till kvadratroten av limit
  ;; p går från start till stopp och markerar alla multiplar som 
  ;; icke prima. Dvs 2, 4, 6, 8, 10, 12 osv (alla multiplar av 2)
  ;; sedan 3, 6, 9, 12, 15 osv (alla multiplar av 3) etc
  ;; det som inte är markera när vi når sqrt(limit)+1 är alltså primtal
  (for ((p (in-range 2 (add1 (integer-sqrt limit)))))
    (when (vector-ref sieve p)
      ;; Markera alla multiplar av p som falska (starta vid p*p)
      (for ((multiple (in-range (* p p) (add1 limit) p)))
        (vector-set! sieve multiple #f)))) ; inte primtal
  ;; returnera sållet till anroparen
  sieve)


;; Returnerar en lista med alla primtal mellan start och stop
(define (primes-between start stop)
  (if (> start stop)
      '() ;Returnerar tomt om start > stop
      (let ([is-prime? (make-sieve stop)])
        (for/list ([n (in-range (max start 2) (add1 stop))]
                   #:when (vector-ref is-prime? n))
          n))))

;; Hjälpmakro för att tajma hur lång tid operationen tog
(require racket/format)
(define-syntax-rule (timeit expr)
  (let ((start (current-inexact-milliseconds)))
    (let ((result expr))
      (printf "Tid: ~a ms\n" (~r (- (current-inexact-milliseconds) start)
              #:group-sep " "     ;tusentalsavskiljare
              #:decimal-sep ","   ;decimalsavskiljare
              #:precision 2))     ;antal decimaler
      result)))  ; returnera svaret

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