CODEWITHSUNDEEP
recursionscheme
user1311286
user1311286

Reputation:

Scheme, stopping my recursion

The function firstnprimes is supposed to return the first n primes. Arguments are n the number of primes, nlist a list from 2-m of integers. and slist is the solution list and is initially empty and is added to and reconstructed each call to firstnprimes.

It works by removing the first number from the list and then removing all multiples of that number from nlist with listminusnonprimes; which I know works. The problem is that I can't control this action, I figure for each pass if slist's length was equal to the number of primes you want then you're done.

Code: 

(define firstnprimes
  (lambda (n nlist slist)
   (let ((slist (cons (car nlist) slist)))
    (if (zero? n)
        slist
        (firstnprimes (- n 1) (listMinusNonprimes (car nlist) (car nlist) nlist) slist)))))


(define listminusnonprimes
     (lambda (num d lst)
       (if (null? lst)
           '()
           (if (= d (car lst))
               (listminusnonprimes num (+ num d) (cdr lst))
               (cons (car lst) (listminusnonprimes num d (cdr lst)))))))

Upvotes: 0

Views: 398

Answers (2)

Rajesh Bhat
Rajesh Bhat

Reputation: 1000

You don't need (let ((slist (cons (car nlist) slist))). Also, use append instead of cons as shown

(define firstnprimes
  (lambda (n nlist slist)
    (if (zero? n)
        slist
        (firstnprimes (- n 1) (listminusnonprimes (car nlist) (car nlist) nlist) (append slist (list (car nlist)))))))

So,

(firstnprimes 2 '(2 4 7 9 21 36) '()) => '(2 7)
(firstnprimes 3 '(2 4 7 9 21 36) '()) => '(2 7 9)

Lots of problems with your implementation though. First, the list has to be in increasing order. Also, the list has to start with a prime number. Also, the number of prime numbers in the nlist has to be less than or equal to n. (firstnprimes 4 '(2 4 7 9 21 36) '()) => '(2 7 9 21) which is wrong

Here is a slightly better implementation of your concept.

(define firstnprimes
  (lambda (n nlist slist)
    (if (or (zero? n) (null? nlist))
        slist
        (firstnprimes (- n 1) (listminusnonprimes (car nlist) (car nlist) nlist) (append slist (list (car nlist)))))))


(define listminusnonprimes
     (lambda (num d lst)
       (if (null? lst)
           '()
           (if (< d (car lst))
               (listminusnonprimes num (+ num d) lst)
               (if (= d (car lst))
                   (listminusnonprimes num (+ num d) (cdr lst))
                   (cons (car lst) (listminusnonprimes num (+ num d) (cdr lst))))))))

Now,

(firstnprimes 2 '(2 4 7 9 21 36) '()) => '(2 7)
(firstnprimes 3 '(2 4 7 9 21 36) '()) => '(2 7 9)
(firstnprimes 4 '(2 4 7 9 21 36) '()) => '(2 7 9)

But the first element still has to be prime though

Upvotes: 0

sxu
sxu

Reputation: 551

Your definition of listminusnonprimes is wrong. Imagine the call (listminusnonprimes 3 3 '(3 5 7 9 11 ...)) (as this would happen after you remove all multiples of 2). Now 3 is removed, and recursively you call (listminusnonprimes 6 3 '(5 7 9 11 ...)), but 6 is not there, so the call does nothing and the result is (3 5 7 9 11 ...).

I would suggest implementing this function using the mod operation.

Upvotes: 1

Related Questions