I am working on coming up with a solution for coming with a list of prime numbers using the Sieve of Eratosthenes. So the program is supposed to find prime numbers up to a specific number "n". I believe I have come up with an incomplete solution but not sure how to proceed from here.
;;;This is a helper function
(define sievehelper
(lambda (list)
;;; This is the base condition where we are comparing
;;; that the divisor is less than the square root of n""
(if (> (car list) (sqrt (car (reverse list))))
'()
;;; If the base condition has not be reached, then send it through
;;; this filter function where not-divisible by will go through
;;; the specified list and only output the list which contains
;;; the numbers that are not divisible by (car list)
(filterfunc (not-divisible-by (car list))
list)))
I have tested the other helper function fliterfunc on its own and it works fine.
;;;; This is the main function that calls the above helper function
(define sieve
(lambda (n)
;;; `makelist` is a helper function to generate the list from 2 to n
(sievehelper (makelist n))))
I have tested the makelist helper function separately and it works fine.
My question is with the helper function "sievehelper" in terms of how to iterate through the different elements in the list as the divisor.
Any help is appreciated. Thank you.
One piece of code that leads to getting stuck is (if ( > (car list) (sqrt (car(reverse list)))), which looks a lot like the loop condition you might use in other languages (and the word "iterate" hints at peeking at other languages, as well).
I would recommend that you start over, with a different strategy.
When you work with lists, you usually want to recurse on their structure alone.
Assume that you have the list of all integers, starting with 2.
As a first step, you want to keep the two, and remove all its multiples from the remainder of the list.
Now, the result of that removal will give you a list that starts with the next prime number - i.e. 3 - so you can repeat the procedure with that partial result which will remove all multiples of 3, and repeat again with that partial result, and so on until there is no more list.
(Note that this is far from as efficient as it could be, but is more a "get started with thinking recursively" level of suggestion. Read Will's answer for more.)
Applying some wishful thinking and assuming that there is a procedure remove-multiples-of which does what it sounds like, this could look like this:
(define (my-sieve-helper ls)
(if (null? ls)
'()
(cons (car ls)
(my-sieve-helper (remove-multiples-of (car ls) (cdr ls))))))
So, remove-multiples-of...
This is the same as keeping all the numbers that are not divisible by a number, so let's dream up another function:
(define (remove-multiples-of x ls) (filter (not-divisible-by x) ls))
where (not-divisible-by x) is a procedure that takes a number and returns whether that number is not divisible by x.
(define (not-divisible-by n) (lambda (x) (not (zero? (remainder x n)))))
And now we can add a suitable wrapper.
I did this:
(define (from-to m n)
(if (> m n)
'()
(cons m (from-to (+ m 1) n))))
(define (my-sieve n) (my-sieve-helper (from-to 2 n)))
Test:
> (my-sieve 100)
'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)