Scheme, first timer first program, simple list removal technique

Question

I have started my hand at writing some scheme code. I am trying to get the first n primes. I plan to do so but first getting a list from 2 to m, and doing the following algorithm. Remove the first number and place in the primes list, remove all #'s from the initial list that are multiples of the number just pulled off, repeat until the size of the primes list equals n.

There are no loops in scheme so I have to use recursion and also modulo will probably help me, how might I go about writing the method "listminusnonprimes"? Also does my code so far look good?

Code:

;Builds a list from [arg] to 2
(define buildlist
 (lambda (m)
 (if (<= m 2)
 '(2)
 (cons m (buildlist(- m 1))))))
;Returns a list from 2 to [arg]
(define listupto
 (lambda (m)
 (reverse (buildlist m))))
;Returns a list with nonprimes based off num removed
(define listminusnonprimes
 (lambda (num list)
 (
;Returns the first n primes
(define firstnprimes
 (lambda (n nlist slist)
 (append (car nlist) slist)
 (if (= n (length slist))
 slist
 (firstnprimes (- n 1) (listMinusNonprimes (car nList) nlist) slit))))

• Tilo Wiklund: Just out of curiosity, wouldn't it be simpler to just build a list of primes by keeping track of the primes found, and for each number see if it is divisible by one of the already found primes (until you've found enough)? Is there a reason (beyond curiosity) for building the initial list?
• BumSkeeter: We are talking about a software sieve and ways we can apply it to find out answer to problems. We were allowed to choose from finding hamming primes, to printing out the fib#'s. But we must implement a sort of sieve. Mine is outlined in the algorithm of removing #'s that a multiples of the first # in the list. I am not sure how to iterate through the list and check each # for its divisibility.
• Tilo Wiklund: You can include the accumulated list of primes as an argument to your function (starting with either an empty or a small list such as the one just containing 2) generating the list, each time you find a new prime, you simply tuck it on to this list of primes before recursing.
• soegaard: @BumSkeeter FWIW you can write loops with do.
• Óscar López: If this is homework, you should tag it accordingly

Answer 1

In your function firstnprimes there is a typo near the end; more importantly it uses append but it is the wrong function to use there. What does append append? If called with two arguments the 2nd of which is a list, what must the first argument be - a list, or a value?

Another problem is your call (append (car nlist) slist) returns new value, a bigger list, but you do nothing with it. slist's value remains unchanged.

What are the two arguments of firstnprimes function, nlist and slist? What are their initial values? Will any two lists do? Obviously not. So, it seems better to define the real top-level function that is safe and easy to use:

(define myfirstnprimes
 (lambda (n)
 (firstnprimes n (listupto ...) (...))))

Something is missing there, isn't it? Some new, hidden parameter?

Now, you ask how to implement

(define listminusnonprimes
 (lambda (num list)
 ....

you call it as (listMinusNonprimes (car nList) nlist) so we know that initially, num is the first element of list; we also know that list is an ordered list of numbers increasing in value. So we just need to compare num with the list's first element:

 (let ((a (car list)))
 (cond
 ( (< num a) ... (listminusnonprimes ...) )
 ( ... )
 ( ... ))) ))

what are the cases? less-then, equal, greater-then, right? All that's left is to fill in the blanks. In particular, if the two are equal, both need to be removed and num changed to the next multiple of the prime; if num is greater, the top element should be kept; otherwise num should be changed to the next multiple of the prime. New missing parameters come into light here (prime... what prime? next multiple... how to find it?); also it isn't clear what does it mean "to keep" and "to remove", right?

About multiples, just write them down in a sequence first: p, 2p, 3p, 4p, .... Now devise a method of finding the next from the previous one. What information will you have to maintain?

About keeping/removing. There are two ways. One will lead to using set-cdr!, another to using cons, and an additional accumulator parameter. Choose any to your liking.

Lastly, your buildlist builds a descending list towards 2, and listupto just reverses it; instead move the former into the latter and have it build the correct list right away from 2 up to the upper limit, held by listupto's argument:

(define (listupto m)
 (let buildlist ((n 2))
 (if (> n m) ...
 (cons n (buildlist ...)))))

Named let is described e.g. here.