This one I will need to study, since it uses new to me Racket stuff. And it is quick. On my machine: > (time (apply + (gb-sieve-of-eratosthenes n))) cpu time: 485 real time: 497 gc time: 118 142913828922
Compare: > (time (apply + (filter prime? (range 2 n)))) cpu time: 9788 real time: 9974 gc time: 1851 142913828922 > (time (apply + (soe n))) cpu time: 1049 real time: 1065 gc time: 311 142913828922 > (time (apply + (sieve-of-eratosthenes n))) cpu time: 266955 real time: 274532 gc time: 218362 142913828922 Machine info in separate email to the list. On 4/24/13 2:17 AM, "Gary Baumgartner" <g...@cs.toronto.edu> wrote: >#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 (in-range 2 (sqrt n))] > #:when (vector-ref A i)) > (for ([j (in-range (sqr i) n i)]) > (vector-set! A j #f))) > > ;; Now all i such that A[i] is true are prime. > (for/list ([i (in-range 2 n)] > #:when (vector-ref A i)) > i)) > >(time (apply + (sieve-of-eratosthenes 2000000))) ____________________ Racket Users list: http://lists.racket-lang.org/users
