Euler 3

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 #3 statement is —

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

My solution is really ugly and is basically dumb-, brute-force.

  <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><span class=‘line’><span class=“kn”>import</span> <span class=“nn”>math</span> </span><span class=‘line’> </span><span class=‘line’><span class=“n”>top_number</span> <span class=“o”>=</span> <span class=“mi”>600851475143</span> </span><span class=‘line’> </span><span class=‘line’><span class=“k”>def</span> <span class=“nf”>is_divisor</span><span class=“p”>(</span><span class=“n”>divisor</span><span class=“p”>):</span> </span><span class=‘line’> <span class=“k”>return</span> <span class=“n”>top_number</span> <span class=“o”>%</span> <span class=“n”>divisor</span> <span class=“o”>==</span> <span class=“mi”>0</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”>divided</span><span class=“p”>):</span> </span><span class=‘line’> <span class=“n”>divisor</span> <span class=“o”>=</span> <span class=“mi”>3</span> </span><span class=‘line’> <span class=“n”>sqrt_divided</span> <span class=“o”>=</span> <span class=“n”>math</span><span class=“o”>.</span><span class=“n”>sqrt</span><span class=“p”>(</span><span class=“n”>divided</span><span class=“p”>)</span> </span><span class=‘line’> <span class=“k”>if</span> <span class=“n”>divided</span> <span class=“o”>==</span> <span class=“mi”>1</span><span class=“p”>:</span> </span><span class=‘line’> <span class=“k”>return</span> <span class=“n”>true</span> </span><span class=‘line’> <span class=“k”>while</span> <span class=“n”>divisor</span> <span class=“o”><=</span> <span class=“n”>sqrt_divided</span><span class=“p”>:</span> </span><span class=‘line’> <span class=“k”>if</span> <span class=“n”>divided</span> <span class=“o”>==</span> <span class=“n”>divisor</span><span class=“p”>:</span> </span><span class=‘line’> <span class=“k”>return</span> <span class=“bp”>True</span> </span><span class=‘line’> <span class=“k”>elif</span> <span class=“n”>divided</span> <span class=“o”>%</span> <span class=“n”>divisor</span> <span class=“o”>==</span> <span class=“mi”>0</span><span class=“p”>:</span> </span><span class=‘line’> <span class=“k”>return</span> <span class=“bp”>False</span> </span><span class=‘line’> <span class=“k”>else</span><span class=“p”>:</span> </span><span class=‘line’> <span class=“n”>divisor</span> <span class=“o”>+=</span> <span class=“mi”>2</span> </span><span class=‘line’> <span class=“k”>return</span> <span class=“bp”>True</span> </span><span class=‘line’> </span><span class=‘line’><span class=“k”>def</span> <span class=“nf”>main</span><span class=“p”>():</span> </span><span class=‘line’> <span class=“n”>count</span> <span class=“o”>=</span> <span class=“mi”>3</span> </span><span class=‘line’> <span class=“n”>go_to</span> <span class=“o”>=</span> <span class=“n”>top_number</span> </span><span class=‘line’> </span><span class=‘line’> <span class=“n”>first_list</span> <span class=“o”>=</span><span class=“p”>[]</span> </span><span class=‘line’> <span class=“k”>while</span> <span class=“n”>count</span> <span class=“o”><=</span> <span class=“n”>go_to</span><span class=“p”>:</span> </span><span class=‘line’> <span class=“k”>if</span> <span class=“n”>is_divisor</span><span class=“p”>(</span><span class=“n”>count</span><span class=“p”>):</span> </span><span class=‘line’> <span class=“n”>first_list</span><span class=“o”>.</span><span class=“n”>append</span><span class=“p”>(</span><span class=“n”>count</span><span class=“p”>)</span> </span><span class=‘line’> <span class=“n”>go_to</span> <span class=“o”>=</span> <span class=“n”>top_number</span> <span class=“o”>/</span> <span class=“n”>count</span> </span><span class=‘line’> <span class=“n”>first_list</span><span class=“o”>.</span><span class=“n”>append</span><span class=“p”>(</span><span class=“n”>go_to</span><span class=“p”>)</span> </span><span class=‘line’> </span><span class=‘line’> <span class=“n”>count</span> <span class=“o”>+=</span> <span class=“mi”>2</span> </span><span class=‘line’> </span><span class=‘line’> <span class=“n”>second_list</span> <span class=“o”>=</span> <span class=“nb”>map</span><span class=“p”>(</span><span class=“n”>is_prime</span><span class=“p”>,</span> <span class=“n”>first_list</span><span class=“p”>)</span> </span><span class=‘line’> <span class=“k”>print</span> <span class=“s”>"</span><span class=“si”>%s</span><span class=“s”>"</span> <span class=“o”>%</span> <span class=“nb”>max</span><span class=“p”>(</span><span class=“nb”>zip</span><span class=“p”>(</span><span class=“n”>second_list</span><span class=“p”>,</span> <span class=“n”>first_list</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=“k”>if</span> <span class=“n”>name</span> <span class=“o”>==</span> <span class=“s”>"main"</span><span class=“p”>:</span> </span><span class=‘line’> <span class=“n”>main</span><span class=“p”>()</span> </span>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
Roberto Selbach
Roberto Selbach
Software Engineer

Ever-learning gopher at HashiCorp.