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

From: SiWi (wimmersimon at googlemail.com)
Date: Sat Aug 1 13:35:22 EDT 2009

Hello PLT Scheme community,
this is my first post here, so please excuse any mistakes.
I'm 16 years old and so far my programming experience has mainly been
in Python.
To learn about functional programming, I just started with Scheme.
For training I tried to convert some prime number generator code from
Python to Scheme.
It's using a sieve algorithm.
The problem is that my Scheme code is about 1000-10000 times slower
than my Python code.
I would greatly appreciate it if you could give me some hints on how
to improve my code.

Python code:

def primes(n):
	sieve=[True for x in range(3,n+1,2)]
	root=n**0.5
	length=len(sieve)
	for i in range(len(sieve)):
		x=2*i+3
		if x>root:
			break
		if sieve[i]:
			for j in range((x*x-x)/2+i,length,x):
				sieve[j]=False
	return [2]+[x*2+3 for x in range(length) if sieve[x]]


Scheme code:

(define (primes n)
  (letrec ((primes-go (lambda (n lst i x nroot) (if (> x nroot)
                                                  lst
                                                  (let ((temp-lst (lst-
remove lst 0 (+ (/ (- (* x x) x) 2) i) x)))
                                                  (primes-go n temp-
lst (+ i 1) (+ (* 2 i) 3) nroot)))))
           (lst-remove (lambda (lst i goal step) (if (null? lst)
                                                        '()
                                                        (if (= goal i)
                                                            (cons #f
(lst-remove (cdr lst) (+ i 1) (+ goal step) step))
                                                            (cons (car
lst) (lst-remove (cdr lst) (+ i 1) goal step))))))
           (list-bool (lambda (n i) (if (>= i n)
                                        '()
                                        (cons #t (list-bool n (+ i
2))))))
           (filter (lambda (lst final i length) (if (>= i length)
                                         final
                                         (if (list-ref lst i)
                                             (filter lst (append final
(list (+ (* 2 i) 3))) (+ i 1) length)
                                             (filter lst final (+ i 1)
length))))))
    (filter (primes-go n (list-bool (+ n 1) 3) 0 3 (sqrt n)) (list 2)
0 (length (list-bool (+ n 1) 3)))))


Posted on the users mailing list.