Euler 7

So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.

Project Euler’s Problem #7 statement is —

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?

It’s a straightforward problem to solve using brute force, but I went with a mixed approach doing some math instead.

  <td class='code'>
    <pre><code class='python'>&lt;span class='line'>&lt;span class="c">#!/usr/bin/python&lt;/span>

</span><span class=‘line’><span class=“kn”>import</span> <span class=“nn”>math</span> </span><span class=‘line’> </span><span class=‘line’><span class=“k”>def</span> <span class=“nf”>is_prime</span><span class=“p”>(</span><span class=“n”>n</span><span class=“p”>):</span> </span><span class=‘line’> <span class=“k”>return</span> <span class=“ow”>not</span> <span class=“p”>(</span><span class=“n”>n</span> <span class=“o”><</span> <span class=“mi”>2</span> <span class=“ow”>or</span> <span class=“nb”>any</span><span class=“p”>(</span><span class=“n”>n</span> <span class=“o”>%</span> <span class=“n”>x</span> <span class=“o”>==</span> <span class=“mi”>0</span> <span class=“k”>for</span> <span class=“n”>x</span> <span class=“ow”>in</span> <span class=“nb”>xrange</span><span class=“p”>(</span><span class=“mi”>2</span><span class=“p”>,</span> <span class=“nb”>int</span><span class=“p”>(</span><span class=“n”>n</span> <span class=“o”>**</span> <span class=“mf”>0.5</span><span class=“p”>)</span> <span class=“o”>+</span> <span class=“mi”>1</span><span class=“p”>)))</span> </span><span class=‘line’> </span><span class=‘line’><span class=“n”>currentMax</span> <span class=“o”>=</span><span class=“mi”>0</span> </span><span class=‘line’><span class=“n”>primes</span> <span class=“o”>=</span> <span class=“mi”>1</span> </span><span class=‘line’><span class=“n”>counter</span> <span class=“o”>=</span> <span class=“mi”>3</span> </span><span class=‘line’> </span><span class=‘line’><span class=“k”>while</span> <span class=“p”>(</span><span class=“n”>primes</span> <span class=“o”><</span> <span class=“mi”>10001</span><span class=“p”>):</span> </span><span class=‘line’> <span class=“k”>if</span> <span class=“p”>(</span><span class=“n”>is_prime</span><span class=“p”>(</span><span class=“n”>counter</span><span class=“p”>)):</span> </span><span class=‘line’> <span class=“n”>currentMax</span> <span class=“o”>=</span> <span class=“n”>counter</span> </span><span class=‘line’> <span class=“n”>primes</span><span class=“o”>+=</span><span class=“mi”>1</span> </span><span class=‘line’> <span class=“n”>counter</span><span class=“o”>+=</span><span class=“mi”>2</span> </span><span class=‘line’> </span><span class=‘line’><span class=“k”>print</span> <span class=“n”>currentMax</span> </span>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

I initially used a dumb brute-force which ended up running fast enough. But reading about primes, I came across this property by which if a number cannot be divided by any number smaller than sqrt(n), it is a prime. That required significantly less tests to be performed inside is_prime, but then again, it had to perform a square root calculation for every number we need to test. In the end, the algorithm above performed slightly better (0.02s to be exact.)

Updated: Thanks to Eduardo Habkost for pointing out the fact that I had mistakenly pasted the wrong version of the script. I fixed the text to reflect that.

Roberto Selbach
Roberto Selbach
Software Engineer

Ever-learning gopher at HashiCorp.