3
\$\begingroup\$

My answer to Project Euler problem 3 (largest prime factor of 600851475143) is below.

Please suggest improvements, style changes, indentation, commenting, naming of "objects", ...

(defun factors (n)
    "return a list with prime factors of n"
    (let ((result))
        (loop while (zerop (rem n 2))           ; do 2
              do (loop while (zerop (rem n 2))
                       do (setf n (/ n 2))
                       do (setf result (cons 2 result))))
        (loop for i from 3 by 2                 ; do 3, 5, 7, 9, ...
              while (>= n (* i i))              ; until square root of what's left of n
              do (loop while (zerop (rem n i))
                       do (setf n (/ n i))
                       do (setf result (cons i result))))
        (if (= n 1) result (cons n result))))   ; if n is not 1 it is also a factor

Questions:

  1. Is the (let ((result)) #| ... (setf result ...) ... |# result) construction acceptable?
  2. I like the result as it is, in reverse; but, other than (reverse result) is there a way to collect factors into result? My attempts with collect i (or collect i into result) would not compile.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$
    – Mast
    Commented Jun 19, 2020 at 8:05

2 Answers 2

4
\$\begingroup\$

Your code is perfectly fine, except for a few nitpicks.

  1. Use push instead of (setf x (conx y x)) for readability.

  2. Use floor instead of rem + / for efficiency.

  3. 1st and 3rd loops are identical, so they should be abstracted into a local flet function.

  4. Use nreverse instead of reverse for the return value. Yes, you can avoid that by using collect combined with nconc but it makes little sense in your specific case.

\$\endgroup\$
2
  • \$\begingroup\$ Thank you. I still gotta learn how to use functions that return two values. Now working on that flet suggestion. \$\endgroup\$
    – pmg
    Commented Jun 18, 2020 at 18:42
  • \$\begingroup\$ see stackoverflow.com/q/22795608/850781 for multi-valued functions \$\endgroup\$
    – sds
    Commented Jun 18, 2020 at 18:57
1
\$\begingroup\$

After direct feedback on sds's answer my code is now

(defun factors (n)
    "return a list with prime factors of n"
    (let ((result))
        (flet ((transfer-factor (fac)
                "transfer available fac from number `n` to list `result`"
                (loop with quotient and remainder
                      do (setf (values quotient remainder)
                               (floor n fac))
                      while (zerop remainder)
                      do (setf n quotient)
                      do (push fac result))))
            (transfer-factor 2)             ; do 2
            (loop for i from 3 by 2         ; do 3, 5, 7, 9, ...
                  while (>= n (* i i))      ; until sqrt of what's left of n
                  do (transfer-factor i)))
        (when (> n 1) (push n result))      ; n may still be a factor
        result))                            ; return complete list

;; in the repl use
;; (first (factors 600851475143))

Incorporated using floor to get quotient and remainder in one operation, incorporated the flet inner function.

I learned to use values and a lot more about the loop construct.
Thanks @sds

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.