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))))

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.