I'm working through some programing puzzles, and one of them was to find the sum of all primes less the 2 million, the new math/number-theory collection (thanks Neil) makes it easy:
#lang racket (require math/number-theory) ;;takes about 4 seconds (apply + (filter prime? (range 1 2000000))) But I thought that spoiled the fun, and I was surely making racket work more then necessary testing each number in the range, so I thought the Sieve of Eratosthenes would be fast and fun: #lang racket ;; Input: an integer n > 1 (define (sieve-of-eratosthenes n) ;; Let A be an array of Boolean values, indexed by integers 2 to n, ;; initially all set to true. ;; for i = 2, 3, 4, ..., √n : ;; when A[i] is true: ;; for j = i², i²+i, i²+2i, ..., n: ;; A[j] := false (define A (make-vector n #t)) (for ([i (range 2 (sqrt n))]) (when (vector-ref A i) (for ([p (range 0 n)]) #:break (> (+ (* i i) (* p i) 1) n) (let ([j (+ (* i i) (* p i))]) (vector-set! A j #f))))) ;; Now all i such that A[i] is true are prime. (filter number? (for/list ([i (range 2 n)]) (when (vector-ref A i) i)))) ;;takes about 17 seconds (time (apply + (sieve-of-eratosthenes 2000000)) But it is dead slow.... Thanks, Jordan ____________________ Racket Users list: http://lists.racket-lang.org/users