Newb: help with factoring function

[Harleqin]

I think that you should first write a function that gives you the next prime number, and then use this function in your factorization function.

[anomaly]

Code: Select all

(defun primep (number)
  (when (> number 1)
    (loop for fac from 2 to (isqrt number) never (zerop (mod number fac)))))

(defun next-prime (number)
  (loop for n from (+ number 1) when (primep n) return n))

(defun factor (num)
  (do* ((factors nil (cons factor factors))
        (current-num num (/ num (apply #'* factors)))
        (factor (do((x (next-prime 0) (next-prime x)))
                     ((or (zerop (rem current-num x)) (= current-num 1)) x))))
         ((= num (apply #'* factors)) (reverse factors))))

Still having the same problem.

Oh, and if you think you recognize the first two functions, I'm still reading Practical Common Lisp .

[Harleqin]

Can you find a replacement for this line:

Code: Select all

        (current-num num (/ num (apply #'* factors)))

which doesn't need to multiply all factors found so far?

[anomaly]

Can you find a replacement for this line:

Code: Select all

        (current-num num (/ num (apply #'* factors)))

which doesn't need to multiply all factors found so far?

Code: Select all

(current-num num (/ current-num (first factors)))

How's that? It works fine, but I'm still having the previously mentioned problem.

Edit: This one is using loop and it works perfectly fine:

Code: Select all

(defun primep (number)
  (when (> number 1)
    (loop for fac from 2 to (isqrt number) never (zerop (mod number fac)))))

(defun next-prime (number)
  (loop for n from (+ number 1) when (primep n) return n))

(defun factor (num)
  (loop for factors = nil then (cons factor factors)
        for current-num = (/ current-num (first factors))
        for factor = (unless (= current-num 1)
                       (loop for x from (next-prime 0) then (next-prime x)
                             until (zerop (rem current-num x))
                             finally (return x)))
        until (= num (apply #'* factors))
        finally (return (reverse factors))))

[Harleqin]

Yes, you can refactor the end test of your outer loop in the same way.

As for your problem: your factor is never changed after it is set for the first time. factors is an ever growing list of 2s.

[gugamilare]

Let me take a look...

Code: Select all

(defun factor (num)
  (do* ((factors nil (cons factor factors))
        (current-num num (/ num (apply #'* factors)))
        (factor (do ((x 2 (+ x 1)))
                     ((or (zerop (rem current-num x)) (= current-num 1)) x))))
         ((= num (apply #'* factors)) (reverse factors))
      ))

This is the version before using primep functions. By the way, finding the next prime is not a good idea, it is faster not to execute some simple divisions then finding the next prime first, because finding the next prime will take much more divisions in general. A good idea, though, is to keep a variable holding the last factor, so you will need to test only for factors equal or greater than the last factor found. But that you can do later, after fixing this.

Now, the problem is the syntax of do. The inner do is evaluated only once and factor is bound (eternally) to it, therefore the lisp ends up divinding undefinitely the number 6 by 2 until the list factors is so long it can't even make a function call - because the function can't handle that many arguments.

The correct version should be:

Code: Select all

(defun factor (num)
  (do* ((factors nil (cons factor factors))
        (current-num num (/ num (apply #'* factors)))
        (factor (do ((x 2 (+ x 1)))
                     ((or (zerop (rem current-num x)) (= current-num 1)) x))
                   (do ((x 2 (+ x 1)))
                     ((or (zerop (rem current-num x)) (= current-num 1)) x))))
         ((= num (apply #'* factors)) (reverse factors))
      ))

Off course, you can bind the inner loop in a flet or a external defun, which would look much better then this mess. But there is one more issue I want to point.

What happens when you call (factor 6) (with the new version off course)?

factors --> nil
current-num --> 6

The inner do returns 2 (the call (rem 6 2) evals to zero).
Note that right now factors is still nil. Therefore (apply #'* factors) is equivalent to (*) and returns 1.
Then the test fails and the do is executed again.

factors --> (2)
current-num --> 3

Then the inner do returns 3.
Note again that here, 3 was still not collected in the list factors, therefore the test fails again.

factors --> (3 2)
current-num --> 1

The inner do returns 2 because (= current-num 1) is true. Then the test succeds and the correct answer is returned.

Well, this version works, but I see something weard here, and I believe you see it as well. The loop version has the same issue.