List of prime numbers from 2 to n (scheme)

Question

I am trying to create a procedure which builds a list of prime numbers from 2 to any number n. Of course, this needs to be done iteratively, but I do not exactly know what I'm doing wrong.

(define (list-2-to-n n)
    (define (iter n result)
        (if (= n 0)
            result
        (if (< n 2)
           '()
            (if (= (remainder n 3) 0)
                (list-2-to-n (- n 1))
            (if (even? n)
                (list-2-to-n (- n 1))
                (iter (- n 1) (cons n result)))))))

    (iter n '())) 

Whenever test cases are passed through the procedure, it always returns ()

Answer 1

what I'm doing wrong.

Let's see. First of all, your indentation is woefully misleading. It really should correctly reflect the code's structure:

(define (list-2-to-n-0 n)       ; a global function
    (define (iter n result)     ; an internal function
        (if (= n 0)             
            result
            (if (< n 2)                        ; **else**
               '()
                (if (= (remainder n 3) 0)
                    (list-2-to-n (- n 1))
                    (if (even? n)              ; **else**
                        (list-2-to-n (- n 1))
                        (iter (- n 1) (cons n result)))))))
    (iter n '())) 

If not, at least you should've clearly marked the alternative clauses with some comments.

Now, you test whether the input number is divisible by 2 or 3, and respond in exactly the same manner. The two cases should really be joined then into one. Also, we can use cond here instead of so many nested ifs:

(define (list-2-to-n-1 n)       ; a global function 
    (define (iter n result)     ; an internal function
        (cond
            ((= n 0)  result)
            ((< n 2)  '())
            ((or (= (remainder n 2) 0) (= (remainder n 3) 0))
              (list-2-to-n (- n 1))       ; calling a global function, and
            (else                         ;   returning its result
              (iter (- n 1)               ; calling internal function, and
                    (cons n result)))))   ;   returning its result
    (iter n '())) 

Calling the global function there means starting the whole process anew - it will call its iter with the initial accumulator argument of (). Your supposedly result-returning case of n==0 is actually unreachable, for any initial value of n above 0, because the case n < 2 will be encountered first, and () will be returned (exactly the observed behaviour).

You shouldn't start anew i.e. you should always call the internal function. You should fix your base case. Last but not least, checking for divisibility by 2 or 3 only won't be enough, already for 5. So let's write isPrime there, and implement it later on:

(define (list-2-to-n-1 n)       ; a global function
    (define (iter n result)     ; an internal function
        (cond
            ((< n 2)  result)
            ((not (isPrime n))
              (iter (- n 1) result))      ; calling internal function, without
            (else                         ;   altering the accumulator
              (iter (- n 1)               ; calling internal function, 
                    (cons n result)))))   ;   altering the accumulator
    (iter n '())) 

isPrime needs to try dividing n by 2,3,... Doesn't need to try dividing by any evens above 2, just odds will be enough. Doesn't need to try out any potential divisor d such that d * d > n, because if n = f * d, f <= d then f*d <= d*d i.e. n <= d*d.

Of course trying dividing by any composite like 9, 15, 77, is superfluous too - if any of those divide n then one of their prime factors 3, 5, 7, 11 divide it too, and we would detect them earlier. So actually, trying dividing by primes only is enough. To be able to do that, you need to restructure your code so that it builds its resulting list of primes in ascending order, and uses its prefix portion not greater than sqrt(k) to test each candidate k.

This is known as trial division algorithm. Then there's a much faster sieve of Eratosthenes.