[plt-scheme] Getting started with Scheme: How can I improve my code for generating prime numbers?

From: Jens Axel Søgaard (jensaxel at soegaard.net)
Date: Sun Aug 2 15:35:40 EDT 2009

Instead of translating the Python program as-is, try to rewrite it
little by little.
To get you started, here is a naive prime sieve in standard PLT Scheme.
(Use the module language).

Try to modify it, to use the same sqrt(n) observation the Python code does.

#lang scheme

; any-divisors-in-list? : number list-of-numbers  ->  boolean
;   If a number in the list divisors is a divisor of n,
;   then true is returned, otherwise false is returned
(define (any-divisors-in-list? n divisors)
  (cond [(null? divisors) #f]
        [(= (remainder n (car divisors)) 0) #t]
        [else (any-divisors-in-list? n (cdr divisors))]))

; primes : number -> list-of-number
;  returns a list of the primes below n
(define (primes n)
  (define numbers-from-0-to-n (build-list n  (λ (x) x)))
  (define numbers-from-2-to-n (cdr (cdr numbers-from-0-to-n)))
  (let loop ([primes '()]
             [non-primes '()]
             [candidates numbers-from-2-to-n])
    (if (null? candidates)
        (let ([n (car candidates)])
          (if (any-divisors-in-list? n non-primes)
              ; n had a divisor
              (loop primes (cons n non-primes) (cdr candidates))
              ; n was a prime
              (loop (cons n primes) non-primes (cdr candidates)))))))

(primes 20)

BTW - Did you take a look at HtDP?

Jens Axel Søgaard

Posted on the users mailing list.