1

I am trying to create a function prime-factors that returns the prime factors of a number. To do so, I created is-prime function, and prime-factors-helper that will do a recursive check of the prime factors.

(defun is-prime (n &optional (d (- n 1))) 
  (if (/= n 1) (or (= d 1)
          (and (/= (rem n d) 0)
               (is-prime  n (- d 1)))) ()))

(defun prime-factors-helper (x n)
   (if (is-prime x) (list x) 
        (if (is-prime n) 
            (if (AND (= (mod x n) 0) (< n (/ x 2)))
                (append (list n) (prime-factors-helper (/ x n) (+ 1 n)))
                (prime-factors-helper x (+ 1 n)))       
            (prime-factors-helper x (+ 1 n)))))

(defun prime-factors (x)
    (prime-factors-helper x 2))

The main function which is prime-factors seem to work for some numbers. However for big numbers it returns "Stack overflow (deep)".

CL-USER 44 : 5 > (prime-factors 66)
(2 3 11)

CL-USER 49 : 5 > (prime-factors 512)
"Stack overflow (deep)"

Can you please tell me why is it returning this error? is there something wrong with the recursive call?

[UPDATE]

I redefined the is-prime function but apparently it is not the problem.

(defun is-prime (x &optional (i 2))
    (if (= x 1) nil
        (if (or (= x 2) (= x 3)) t
            (if (<= i (sqrt x))
                (if (= (mod x i ) 0) nil
                    (is-prime x (+ i 1)))
                t))))



(defun prime-factors-helper (x n)
   (if (is-prime x) 
       (list x) 
       (if (is-prime n) 
            (if (AND (= (mod x n) 0) (<= n (/ x 2)))
                (cons n (prime-factors-helper (/ x n) n))
                (prime-factors-helper x (+ 1 n)))       
            (prime-factors-helper x (+ 1 n)))))

Optimisation question

I have another problem of optimisation. When I have a big number such as 123456789, I get this error message Stack overflow (stack size 261120). I believe because since the correct answer is (3 3 3607 3803), my program once it constructs the list with the two first elements (3 3), it will take so long to find the next prime factor. How can I optimise my code?

Improve this question
8
  • 1
    That means your recursion isn't stopping. The only time you seem to stop recursing is when x is prime. If that never happens, the recursion will go on forever. Have you tested is-prime to make sure it's correct? Commented Mar 18, 2018 at 14:06
  • @Carcigenicate Yes I tested it. It is correct Commented Mar 18, 2018 at 14:15
  • @Carcigenicate it is not the is-prime function. I defined it differently but still I have the exact same problem. Please check the new update where I put the new definition of the is-prime function Commented Mar 18, 2018 at 16:32
  • 1
    Then you'll need to find out why the recursion isn't stopping. (prime-factors 512) could also just be "too big" of a problem to solve using unoptimized recursion. Commented Mar 18, 2018 at 16:38
  • 1
    @Carcigenicate I solved it. Actually it does not only that for 512. It happens for all the multiples of 2. In the condition (if (AND (= (mod x n) 0) (< n (/ x 2))) if the number is multiple of 2 it will never enter this condition even though it has to. The reason is that I put <. It should be <=. So (if (AND (= (mod x n) 0) (<= n (/ x 2))). Thanks for your help Commented Mar 18, 2018 at 16:54

1 Answer 1

Reset to default
5

Some general remarks about your code:

(defun is-prime (x &optional (i 2))
    (if (= x 1) nil
        (if (or (= x 2) (= x 3)) t
            (if (<= i (sqrt x))
                (if (= (mod x i ) 0) nil
                    (is-prime x (+ i 1)))
                t))))

(defun prime-factors-helper (x n)
   (if (is-prime x) (list x) 
        (if (is-prime n) 
            (if (and (= (mod x n) 0) (<= n (/ x 2)))
                (append (list n) (prime-factors-helper (/ x n) (+ 1 n)))
                (prime-factors-helper x (+ 1 n)))       
            (prime-factors-helper x (+ 1 n)))))


(defun prime-factors (x)
    (prime-factors-helper x 2)) 

CL-USER 44 : 5 > (prime-factors 66)
(2 3 11)

A few things you should improve: indentation, code formatting, proper use of the REPL and choice of Lisp functions:

Code indentation and formatting

Let's start with indentation and formatting. The usual indentation would be:

(defun is-prime (x &optional (i 2))
  (if (= x 1)
      nil
    (if (or (= x 2) (= x 3))
        t
      (if (<= i (sqrt x))
          (if (= (mod x i ) 0)
              nil
            (is-prime x (+ i 1)))
        t))))

(defun prime-factors-helper (x n)
  (if (is-prime x)
      (list x) 
    (if (is-prime n) 
        (if (and (= (mod x n) 0) (<= n (/ x 2)))
            (append (list n) (prime-factors-helper (/ x n) (+ 1 n)))
          (prime-factors-helper x (+ 1 n)))
      (prime-factors-helper x (+ 1 n)))))


(defun prime-factors (x)
  (prime-factors-helper x 2))

Improving the code

Now we can rewrite the first two functions:

Use case to compare for numbers and then you can rewrite the if expression to a logic expression using or, and and not.

(defun is-prime (x &optional (i 2))
  (case x
    (1     nil)
    ((2 3) t)
    (t     (or (not (<= i (sqrt x)))
               (and (/= (mod x i) 0)
                    (is-prime x (+ i 1)))))))

Next we reduce the indentation level by using cond.

(append (list foo) bar) is just (cons foo bar).

We also can get rid of one if.

(defun prime-factors-helper (x n)
  (cond ((is-prime x)
         (list x))
        ((and (is-prime n)
              (= (mod x n) 0)
              (<= n (/ x 2)))
         (cons n (prime-factors-helper (/ x n) (+ 1 n))))
        (t (prime-factors-helper x (+ 1 n)))))

Test function

Now we need to test it:

(defun test (&optional (n 20))
  (loop for i from 2 below n
        for factors = (prime-factors i)
        do (print (list i
                        (= (reduce #'* factors) i)
                        (cons '* factors)))))

There is a problem: fix it!

As you can see there is a problem left... I had to break the code from an endless loop when we compute the factors for 8.

CL-USER 51 > (test)

(2 T (* 2)) 
(3 T (* 3)) 
(4 T (* 2 2)) 
(5 T (* 5)) 
(6 T (* 2 3)) 
(7 T (* 7)) 
Break.
  1 (continue) Return from break.
  2 (abort) Return to top loop level 0.

But that one is easy to fix and left as an exercise.

The REPL.

When you have a prompt like this in LispWorks

CL-USER 44 : 5 >

it means that you are five (!) levels deep in breaks.

Time to get to the top-level repl by entering the :top command:

CL-USER 44 : 5 > :top

CL-USER 45 >
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Thank you for your remarks. I have already fixed the problem of the multiples of 2, I only forgot to post it. However, I discovered another problem of optimisation. Can you please check my new question in my post.
@Benz: make a new question, don't add to an existing one
I just did. Can you please have a look. stackoverflow.com/questions/49352407/…

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.