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


;; Testkörning
(primes-between 10 50)