[plt-scheme] Getting started with Scheme: How can I improve my code for generating prime numbers?
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)))))