# [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)
primes
(let ([n (car candidates)])
(if (any-divisors-in-list? n non-primes)
(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. Previous message: [plt-scheme] Getting started with Scheme: How can I improve my code for generating prime numbers? Next message: [plt-scheme] Getting started with Scheme: How can I improve my code for generating prime numbers? Messages sorted by: [date] [thread] [subject] [author]