# euler 41 pandigital primes

Mar 22, 2015

Yet another brute-force solution, pushing the line a bit at 1991 seconds. But hey, it works, and was quick to write, so …

``````(defparameter *max-num-limit* 1000000000)
(defparameter *all-numbers* (make-array (list *max-num-limit*) :element-type 'bit :initial-element 1))

(defun mark-primes (&optional (n *max-num-limit*))
;; 0 and 1 are not prime
(mark-not-prime 0)
(mark-not-prime 1)
;; Mark 2 as prime, then do the following:
;; (1) Mark all multiples of the prime number,
;; (2) Find next available prime number, mark it as prime,
;; Repeat (1) until n
(let ((prime 2))
(loop while (< prime n) do
(mark-prime-multiples prime n)
(setf prime (find-next-prime prime n)))))

(defun mark-not-prime (idx)
(setf (bit *all-numbers* idx) 0))

(defun mark-prime-multiples (prime limit)
(do ((i (* prime 2) (+ i prime)))
((>= i limit))
(mark-not-prime i)))

(defun find-next-prime (prev-prime limit)
(do ((i (1+ prev-prime) (1+ i)))
((or (= i limit) (= 1 (bit *all-numbers* i))) i)))

(defun is-prime (n)
(= 1 (bit *all-numbers* n)))

(defun get-num-digits (n)
(ceiling (log n 10)))

(defun is-pandigital (n)
(let* ((num-digits (get-num-digits n))
(digits (make-array num-digits :element-type 'bit :initial-element 0)))
(loop while (and (> n 0)
(> (mod n 10) 0)
(<= (mod n 10) num-digits)) do
(setf (bit digits (1- (mod n 10))) 1)
(setf n (floor (/ n 10))))
(= (length digits) (count 1 digits))))

(defun euler41 ()
(mark-primes)
(do ((n 987654321 (1- n)))
((and (is-pandigital n) (is-prime n)) n)))
``````

Everything is wrapped up in the call to `(euler41)`.