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
  (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
  (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))))
  ;; 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))