4
\$\begingroup\$

To start with Common Lisp I am doing Project Euler using this language. Usually I manage to solve problems but I am quite sure that my code is not as efficient as it could be in Common Lisp. That is why I need a review from experienced lispers.

This is my code for problem 35. Please offer any improvements.

(defun prime-p (n)
  (cond
    ((= n 1) nil)
    ((= n 2) t)
    ((evenp n) nil)
    (t (loop for i from 3 to (isqrt n) by 2
      never (zerop (mod n i))))))

(defun list->num (lst)
  (loop for i in lst
       for p = (- (length lst) 1) then (- p 1)
       sum (* i (expt 10 p))))

(defun num->list (n)
  (loop for c across (write-to-string n)
       collect (parse-integer (string c))))

(defun rotate (lst)
  (append (last lst) (butlast lst)))

(defun number-rotations (n)
  (let* ((digits (num->list n))
         (digits-count (length digits)))
    (loop repeat digits-count
       for rotated = digits then (rotate rotated)
       collect (list->num rotated))))

(defun problem-35 (limit)
  (let ((hash-primes (make-hash-table)))
    (loop for n from 1 to limit
       if (prime-p n)
       do (setf (gethash n hash-primes) t))
    (loop for p being the hash-keys in hash-primes
       if (loop for n in (number-rotations p)
         always (gethash n hash-primes))
       collect p)))
\$\endgroup\$
4
\$\begingroup\$

In list->num you can count down with something like for i downfrom n.

(defun num->list (n)
  (loop for c across (write-to-string n)
        collect (parse-integer (string c))))

In above function you can just collect (digit-char-p c). The function returns the digit value as a number.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Consider giving common lisp some optimizing hints. Adding a single (declare (fixnum n) takes the runtime (on my machine) of (euler-35 1000000) from 1.2 seconds to 0.83 seconds:

(defun prime-p (n)
  (declare (fixnum n))
  (cond
    ((= n 1) nil)
    ((= n 2) t)
    ((evenp n) nil)
    (t (loop for i from 3 to (isqrt n) by 2
      never (zerop (mod n i))))))
|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

If you treat primes below 1,000,000, memorize primes below 1,000. Use strings in rotation operation.

(defun print-rotation (number)
  (let* ((str (format nil "~a" number))
         (strstr (concatenate 'string str str)))
    (loop for i below (length str) do
      (format t "~a~%" (parse-integer (subseq strstr i (+ i (length str))))))))
|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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