Sort prime factors in ascending order Scheme

Question

I am new to Scheme and I want to sort the prime factors of a number into ascending order. I found this code, but it does not sort.

(define (primefact n)
 (let loop ([n n] [m 2] [factors (list)])
  (cond [(= n 1) factors]
      [(= 0 (modulo n m)) (loop (/ n m) 2 (cons m factors))]
      [else (loop n (add1 m) factors)])))

Can you please help. Thank you

Answer 1

I would say it sorts, but descending. If you want to sort the other way, just reverse the result:

(cond [(= n 1) (reverse factors)]

Answer 2

Usually when you need something sorted in the order you get them you can cons them like this:

(define (primefact-asc n)  
  (let recur ((n n) (m 2))
    (cond ((= n 1) '())
          ((= 0 (modulo n m)) (cons m (recur (/ n m) m))) ; replaced 2 with m
          (else (recur n (+ 1 m))))))

Note that this is not tail recursive since it needs to cons the result, but since the amount of factors in an answer is few (thousands perhaps) it won't matter much.

Also, since it does find the factors in order you don't need to start at 2 every round but the number you found.

Answer 3

Which dialect of Scheme is used?

Three hints:

You need only to test for divisors less equal as the square-root of your Number. a * b = N ; a < b ---> a <= sqrt( N ).

If you need all Prime-Numbers less some Number, you should use the sieve of eratothenes. See Wikipedia.

Before you start to write a program, look in Wikipedia.

If