· haskell

Haskell: Getting the nth element in a list

I started trying to solve some of the Project Euler problems as a way to learn a bit of Haskell and problem 7 is defined like so:

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 10 001st prime number?

I read that the Sieve of Eratosthenes is a useful algorithm for working out all the prime numbers and there’s a page on the Literate Programs wiki explaining how to derive them using it.

The most naive implementation of all the primes ends up reading like this:


primes = 2 : sieve [3,5..]  where
    sieve []     = []
    sieve (p:xs) = p : sieve (xs `minus` [p,p+2*p..])

That gives an infinite sequence of all the prime numbers but I wanted to be able to specifically pick the 10,001st prime number which I assumed would be named ‘nth’ or something like that.

As it turns out we actually need to use the ‘!!’ operator which I found out from Mark Chu-Carroll’s blog post:


*Main> :t (!!)
(!!) :: [a] -> Int -> a

problem_7 = primes !! 10000 -- 0 indexed so we need to get the position one before 10,001

It takes a while to run but we end up with the answer:


*Main> problem_7
104743
  • LinkedIn
  • Tumblr
  • Reddit
  • Google+
  • Pinterest
  • Pocket