title: nth Prime, and Prime Factors
body: <p>Going through the Haskell tutorial, it said to write a function 'isPrime' to determine if a number is a prime number.</p>
  
  <p>I came up with:</p>
  
  <pre><code>isPrime :: Integer -&gt; Bool
  isPrime n = factors n == [1,n]
      where factors n = [x | x &lt;- [1..n], n `mod` x == 0]
  </code></pre>
  
  <p>which works.</p>
  
  <p>But how would I go about asking for the nth prime number -- as in, the 100th prime number is 541?</p>
  
  <p>Playing around further with primes, I found a list of Prime Factors like this:</p>
  
  <pre><code>primeFactors :: Integer -&gt; [Integer]
  primeFactors n = filter prime (factors n)
      where factors n = [x | x &lt;- [1..n], n `mod` x == 0]
            prime n = factors n == [1,n]
  </code></pre>
  
  <p>and that works, too.</p>
  
  <p>However, when you put in a very large number, you get significant lag time.</p>
  
  <p>As an example, it does these just fine:</p>
  
  <pre><code>ghci &gt; primeFactors 419
  [419]
  
  ghci &gt; primeFactors 5698
  [2,7,11,37]                 -- did this one really fast...
  
  ghci &gt; primeFactors 76586
  [2,149,257]                 -- and this one really fast... 
  
  ghci &gt; primeFactors 876350
  [2,5,17,1031]               -- it hung up just a hair with this one...
  
  ghci &gt; primeFactors 4287635
  [5,11,19,373]               -- hung up a little bit longer here...
  
  ghci &gt; primeFactors 34598274
  [2,3,5766379]               -- hung up for quite a while here...
  
  ghci &gt; primeFactors 208346758
  [2,104173379]               -- and for a very long time with this one!
  </code></pre>
  
  <p>The tutorial suggested finding the prime factors of 62451532000, and on that one, I'm still waiting, after somewhere around 5 minutes.</p>
  
  <p>What is causing the lag time, and what would be the best way to speed this up?</p>