November 8, 2008

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?


This Common Lisp solution uses the Sieve of Eratosthenes algorithm to find all the prime numbers under a million then returns the 10001st prime.

(defconstant +max+ 1000000)

(defun range (start end)
"Creates a list of integers from start to end"
(loop for i from start to end collect i))

(defun e.6 ()
(let ((limit (sqrt +max+))
(lst (range 2 +max+)))
(loop for i in lst until (> i limit) do
;; Delete all multiples of i from the list
(delete-if #'(lambda (x)
(and (not (eq x i))
(zerop (mod x i))))
lst))
;; The resulting list is a list of all prime numbers
;; up to +max+. Get the 10001st prime number
(nth 10000 lst)))

0 comments: