No Permission

Ah, Problem 7, the one we knew was coming.

“What is the 10001st prime number?”

The basics are simple enough. Brute force a primality test via trial division and use the test to find 10001 prime number. So I did that, got the answer.

But it took 2:24 on my netbook, and the rule of Project Euler is that it should take less than 1:00.

So it was time to optimize! I started with the simplest optimization, limiting the upper bound of the trial division in the square root of the number being tested. If you’ve made it that far without finding a factor, you’re not going to (other than the number itself, of course), so it’s prime.

Once I added that, the time dropped to under 4 seconds, which surprised me. I didn’t expect that dramatic a drop from such a basic optimization. Lesson learned there. Sometimes it’s worth just a little more effort to make things much, much faster.

It’s also worth noting, however, that there a number of other simple optimizations I’m not adding in since I’m already well under the goal.

Called by “euler7:nthprime(10001,2)” I’m seeding it with the first prime there. In most of these I could eliminate one of my seed parameters by having alternate versions of the functions for the base case, but I do it this way to simplify the code itself.

Prime Grade A Code-

 -module(euler7).
 -import(math).
 -export([nthprime/2]).

nthprime(N,Prevprime) ->
   if N >= 2 ->
        NthPrime = findprime(Prevprime+1),
        nthprime(N-1,NthPrime);
   true ->
       Prevprime
   end.     

findprime(Start) ->
   Max = math:sqrt(Start),
   Prime = isprime(Start,2,Max),
   if Prime == true ->
      Start;
   true ->
          findprime(Start+1)
   end.

isprime(N,PFactor,Max)->
   if PFactor =< Max ->
          if  N rem PFactor == 0 ->
              false;
          true ->
              isprime(N,PFactor+1,Max)
          end;
    true ->
          true
    end.