-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathproject-euler-answers.html
395 lines (344 loc) · 32.3 KB
/
project-euler-answers.html
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
<head>
<!-- 2022-W11-4 02:12 -->
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>Project Euler Answers</title>
<meta name="author" content="Inanna" />
<meta name="description" content="Answers to project euler problems." />
<meta name="generator" content="Org Mode" />
<link href="/site.css" rel="stylesheet" type="text/css" /><link href="images/website-icon.png" rel="icon" />
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
displayAlign: "center",
displayIndent: "0em",
"HTML-CSS": { scale: 100,
linebreaks: { automatic: "false" },
webFont: "TeX"
},
SVG: {scale: 100,
linebreaks: { automatic: "false" },
font: "TeX"},
NativeMML: {scale: 100},
TeX: { equationNumbers: {autoNumber: "AMS"},
MultLineWidth: "85%",
TagSide: "right",
TagIndent: ".8em"
}
});
</script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS_HTML"></script>
</head>
<body>
<div id="preamble" class="status">
<div><a href="/index.html"><img alt="An abstract logo representing a series of three assembly line stamping machines with the words CONS, DEV, and embalzoned in white on each machine." id="site-logo" src="/images/website-logo.png" /></a></div>
</div>
<div id="content" class="content">
<h1 class="title">Project Euler Answers</h1>
<div id="table-of-contents" role="doc-toc">
<h2>Table of Contents</h2>
<div id="text-table-of-contents" role="doc-toc">
<ul>
<li><a href="#org4bd1646">Summary</a></li>
<li><a href="#org68d76ed">1: Multiples of 3 or 5</a>
<ul>
<li><a href="#org742b2d9">Brute Force Answer</a></li>
<li><a href="#org8dd4943">Optimized Answer</a></li>
</ul>
</li>
<li><a href="#orgc747142">2: Even Fibonacci Numbers</a></li>
<li><a href="#org8555275">3: Largest Prime Factor</a>
<ul>
<li><a href="#orgedc7a57">Finding Prime Numbers</a>
<ul>
<li><a href="#org162fcdc">Checking for Divisibility</a></li>
<li><a href="#orgbb7789a">Sieve of Eratosthenes</a></li>
<li><a href="#orgba66997">A More Ugly Approach</a></li>
</ul>
</li>
</ul>
</li>
</ul>
</div>
</div>
<div id="outline-container-org4bd1646" class="outline-2">
<h2 id="org4bd1646">Summary</h2>
<div class="outline-text-2" id="text-org4bd1646">
<p>
My answers to various project Euler problems. I occasionally will be doing these because they are fun and pretty entertaining.
</p>
</div>
</div>
<div id="outline-container-org68d76ed" class="outline-2">
<h2 id="org68d76ed">1: Multiples of 3 or 5</h2>
<div class="outline-text-2" id="text-org68d76ed">
<dl class="org-dl">
<dt>source</dt><dd><a href="https://projecteuler.net/problem=1">https://projecteuler.net/problem=1</a></dd>
</dl>
</div>
<div id="outline-container-org742b2d9" class="outline-3">
<h3 id="org742b2d9">Brute Force Answer</h3>
<div class="outline-text-3" id="text-org742b2d9">
<p>
Here I use the simple brute force answer, which is to generate a list to 1000 and then get the multiples of three and five in that list using the modulus operator. It's pretty short but I probably can code golf-it and optimize it quite a bit.
</p>
<div class="org-src-container">
<pre class="src src-clojure"><span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">letfn</span> <span style="color: #bbb;">[</span><span style="color: #494949;">(</span>divisible? <span style="color: #bbb;">[</span>n div<span style="color: #bbb;">]</span> <span style="color: #bbb;">(</span>zero? <span style="color: #494949;">(</span>mod n div<span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span><span style="color: #bbb;">]</span>
<span style="color: #bbb;">(</span><span style="color: #E53935; font-style: italic;">->></span> <span style="color: #494949;">(</span>range 1000<span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>filter #<span style="color: #bbb;">(</span><span style="color: #E53935; font-style: italic;">or</span> <span style="color: #494949;">(</span>divisible? <span style="font-style: italic;">%</span> 3<span style="color: #494949;">)</span> <span style="color: #494949;">(</span>divisible? <span style="font-style: italic;">%</span> 5<span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>apply +<span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
</pre>
</div>
</div>
</div>
<div id="outline-container-org8dd4943" class="outline-3">
<h3 id="org8dd4943">Optimized Answer</h3>
<div class="outline-text-3" id="text-org8dd4943">
<p>
So instead of that approach there's a much faster one using recursion.<label class="sidenote-number" for="1"><sup>1</sup></label><input checked="checked" id="1" style="display:none" type="checkbox" /><span class="sidenote"><span class="sidenote-number"> 1</span> the n-ary function syntax for Clojure is really nice here, allowing me to use default arguments.</span>
</p>
<div class="org-src-container">
<pre class="src src-clojure"><span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">letfn</span> <span style="color: #bbb;">[</span><span style="color: #494949;">(</span>multiples-to
<span style="color: #bbb;">(</span><span style="color: #494949;">[</span>n mul<span style="color: #494949;">]</span> <span style="color: #494949;">(</span>multiples-to n mul <span style="color: #bbb;">[]</span> 1<span style="color: #494949;">)</span><span style="color: #bbb;">)</span>
<span style="color: #bbb;">(</span><span style="color: #494949;">[</span>n mul l i<span style="color: #494949;">]</span>
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">let</span> <span style="color: #bbb;">[</span>multiple <span style="color: #494949;">(</span>* i mul<span style="color: #494949;">)</span><span style="color: #bbb;">]</span>
<span style="color: #bbb;">(</span><span style="color: #E53935; font-style: italic;">if</span> <span style="color: #494949;">(</span>> multiple n<span style="color: #494949;">)</span> l <span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">recur</span> n mul <span style="color: #bbb;">(</span>conj l multiple<span style="color: #bbb;">)</span> <span style="color: #bbb;">(</span>inc i<span style="color: #bbb;">)</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span><span style="color: #bbb;">]</span>
<span style="color: #bbb;">(</span><span style="color: #E53935; font-style: italic;">->></span> <span style="color: #494949;">(</span>concat <span style="color: #bbb;">(</span>multiples-to 1000 3<span style="color: #bbb;">)</span>
<span style="color: #bbb;">(</span>multiples-to 1000 5<span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
distinct
<span style="color: #494949;">(</span>apply +<span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
</pre>
</div>
<p>
This answer unfortunately only really shows improvements in efficiency when the multiples are around 100 or 300, rather than 3 and 5. In fact, it is actually considerably less efficient than the first "brute-force" answer in the 3-5 case.
</p>
</div>
</div>
</div>
<div id="outline-container-orgc747142" class="outline-2">
<h2 id="orgc747142">2: Even Fibonacci Numbers</h2>
<div class="outline-text-2" id="text-orgc747142">
<dl class="org-dl">
<dt>source</dt><dd><a href="https://projecteuler.net/problem=3">https://projecteuler.net/problem=3</a></dd>
</dl>
<p>
This just gets even fib numbers. There's not much to optimize here because the process is both fairly simple and (as far as I can tell) cannot be changed.
</p>
<div class="org-src-container">
<pre class="src src-clojure"><span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">letfn</span> <span style="color: #bbb;">[</span><span style="color: #494949;">(</span>fib
<span style="color: #bbb;">(</span><span style="color: #494949;">[</span>max-num<span style="color: #494949;">]</span> <span style="color: #494949;">(</span>fib max-num <span style="color: #bbb;">[</span>1 2<span style="color: #bbb;">]</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span>
<span style="color: #bbb;">(</span><span style="color: #494949;">[</span>max-num lst<span style="color: #494949;">]</span>
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">let</span> <span style="color: #bbb;">[</span>next <span style="color: #494949;">(</span>apply + <span style="color: #bbb;">(</span>take 2 lst<span style="color: #bbb;">)</span><span style="color: #494949;">)</span><span style="color: #bbb;">]</span>
<span style="color: #bbb;">(</span><span style="color: #E53935; font-style: italic;">if</span> <span style="color: #494949;">(</span>> next max-num<span style="color: #494949;">)</span>
lst
<span style="color: #494949;">(</span>fib max-num <span style="color: #bbb;">(</span>cons next lst<span style="color: #bbb;">)</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span><span style="color: #bbb;">]</span>
<span style="color: #bbb;">(</span><span style="color: #E53935; font-style: italic;">->></span> <span style="color: #494949;">(</span>fib 4000000<span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>filter even?<span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>apply +<span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
</pre>
</div>
</div>
</div>
<div id="outline-container-org8555275" class="outline-2">
<h2 id="org8555275">3: Largest Prime Factor</h2>
<div class="outline-text-2" id="text-org8555275">
<dl class="org-dl">
<dt>source</dt><dd><a href="https://projecteuler.net/problem=2">https://projecteuler.net/problem=2</a></dd>
</dl>
<p>
The goal is to find the largest prime factor of a number. To start we will first begin by creating a function that finds a number of primes up to the target value divided by 2. This is because the target value will, ultimately, be at most \(n \times 2\).
</p>
</div>
<div id="outline-container-orgedc7a57" class="outline-3">
<h3 id="orgedc7a57">Finding Prime Numbers</h3>
<div class="outline-text-3" id="text-orgedc7a57">
<p>
To start out we find a list of prime numbers. A neat feature of prime numbers is that to test a number for primality you both only need to test for the division of a number by other prime numbers up to the square root of the value, for the largest number will be at most the square root.
</p>
</div>
<div id="outline-container-org162fcdc" class="outline-4">
<h4 id="org162fcdc">Checking for Divisibility</h4>
<div class="outline-text-4" id="text-org162fcdc">
<p>
To start off, and to make our code more clear, we define a small predicate called <code>divisible?</code> which checks if a number is divisible by some other number. While it doesn't really shorten the code all that much, it adds clarity to the code
</p>
<div class="org-src-container">
<pre class="src src-clojure" id="org2013107"><span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">defn</span> <span style="font-weight: bold; font-style: italic;">divisible?</span> <span style="color: #bbb;">[</span>num div<span style="color: #bbb;">]</span> <span style="color: #bbb;">(</span>zero? <span style="color: #494949;">(</span>mod num div<span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
</pre>
</div>
</div>
</div>
<div id="outline-container-orgbb7789a" class="outline-4">
<h4 id="orgbb7789a">Sieve of Eratosthenes</h4>
<div class="outline-text-4" id="text-orgbb7789a">
<p>
The most elegant solution would be the sieve of Eratosthenes. The logic behind it is fairly simple:
</p>
<ol class="org-ol">
<li>all natural numbers are either primes or a composite of a number of primes</li>
<li>a number is prime if no prime divisor less than itself exists</li>
<li>therefore, if one creates a list from \(2...n\) and takes the head of the list and filter out all divisors, add the head to a second list, and continue until the list is emptied the second list should contain the primes from \(2...n\)</li>
</ol>
<p>
As you can see, it follows that the list generated will be entirely comprised of prime numbers.
</p>
<p>
To solve this we can implement a lazy sieve of Eratosthenes. Lazy in that the resulting sequence will be infinite.
</p>
<div class="org-src-container">
<pre class="src src-clojure" id="orgfd069df"><span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">defn</span> <span style="font-weight: bold; font-style: italic;">seive</span>
<span style="color: #bbb;">(</span><span style="color: #494949;">[]</span> <span style="color: #494949;">(</span>seive <span style="color: #bbb;">(</span>drop 2 <span style="color: #494949;">(</span>range<span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span>
<span style="color: #bbb;">(</span><span style="color: #494949;">[</span>l<span style="color: #494949;">]</span>
<span style="color: #494949;">(</span>lazy-seq
<span style="color: #bbb;">(</span><span style="color: #E53935; font-style: italic;">let</span> <span style="color: #494949;">[</span><span style="color: #bbb;">[</span>x & xs<span style="color: #bbb;">]</span> l<span style="color: #494949;">]</span>
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">if</span> <span style="color: #bbb;">(</span>empty? xs<span style="color: #bbb;">)</span>
<span style="color: #bbb;">[</span>x<span style="color: #bbb;">]</span>
<span style="color: #bbb;">(</span>cons x <span style="color: #494949;">(</span>seive <span style="color: #bbb;">(</span>filter #<span style="color: #494949;">(</span>not <span style="color: #bbb;">(</span>divisible? <span style="font-style: italic;">%</span> x<span style="color: #bbb;">)</span><span style="color: #494949;">)</span> xs<span style="color: #bbb;">)</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">def</span> <span style="font-style: italic;">primes</span> <span style="color: #bbb;">(</span>seive<span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
</pre>
</div>
<p>
Unfortunately this does not work for what we want. It is very beautiful, and I wish it did work, but because of the specific features of TCO in Clojure <label class="sidenote-number" for="2"><sup>2</sup></label><input checked="checked" id="2" style="display:none" type="checkbox" /><span class="sidenote"><span class="sidenote-number"> 2</span> Even with the <code>recur</code> special form.</span> it doesn't actually produce TCO code, and, because it is recursive, will end up causing a stack overflow.
</p>
<p>
However, because of the lazy list semantics you can take a nearly infinite series of primes from it, assuming you only increase your requested list size by one each time you take from it. This is interesting, though unfortunately not something I can really use.
</p>
</div>
</div>
<div id="outline-container-orgba66997" class="outline-4">
<h4 id="orgba66997">A More Ugly Approach</h4>
<div class="outline-text-4" id="text-orgba66997">
<p>
So in order to solve this we can rewrite the is-prime function to, rather than generating a list from 0 to \(n\) and then filtering it, simply loop until a value at the range of the prime number is found. This ensures that the space complexity of it is \(O(\log(n))\) rather than \(O(n)\), though does not change the time complexity.
</p>
<p>
First we define an <a href="https://clojure.org/reference/atoms">atom</a> to <a href="https://en.wikipedia.org/wiki/Memoization">memoize</a> our primes called <code>found-primes</code>, and initialize it with the first prime number, 2.
</p>
<div class="org-src-container">
<pre class="src src-clojure" id="orgb208c28"><span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">def</span> ^<span style="color: #E53935;">:private</span> <span style="font-style: italic;">found-primes</span>
<span style="color: #a4a4a4; font-style: italic;">"A map of all primes that have been found thus far by the system"</span>
<span style="color: #bbb;">(</span>atom #<span style="color: #494949;">{</span>2<span style="color: #494949;">}</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">def</span> ^<span style="color: #E53935;">:private</span> <span style="font-style: italic;">max-prime</span> <span style="color: #bbb;">(</span>atom 2<span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
</pre>
</div>
<p>
Next we define an <code>is-prime?</code> predicate which will test if a value is prime by iterating over the list of primes that are less than the square root of the new value. This is basically the same as the sieve of Eratosthenes applied to a single element. Below is the function itself, don't worry, we will break it down.
</p>
<div class="org-src-container">
<pre class="src src-clojure" id="org8572985"><span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">defn</span> <span style="font-weight: bold; font-style: italic;">is-prime?</span>
<span style="color: #bbb;">(</span><span style="color: #494949;">[</span>n<span style="color: #494949;">]</span> <span style="color: #494949;">(</span>is-prime? n <span style="color: #E53935;">false</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span>
<span style="color: #bbb;">(</span><span style="color: #494949;">[</span>n contiguous?<span style="color: #494949;">]</span>
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">let</span> <span style="color: #bbb;">[</span>max-div <span style="color: #494949;">(</span>int <span style="color: #bbb;">(</span>inc <span style="color: #494949;">(</span><span style="color: #E53935;">Math</span>/sqrt n<span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span><span style="color: #bbb;">]</span>
<span style="color: #bbb;">(</span><span style="color: #E53935; font-style: italic;">letfn</span> <span style="color: #494949;">[</span><span style="color: #bbb;">(</span>div? <span style="color: #494949;">[</span>n<span style="color: #494949;">]</span>
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">->></span> @found-primes
<span style="color: #bbb;">(</span>take-while #<span style="color: #494949;">(</span>> max-div <span style="font-style: italic;">%</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span>
<span style="color: #bbb;">(</span>some #<span style="color: #494949;">(</span>divisible? n <span style="font-style: italic;">%</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span>
not<span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">]</span>
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">cond</span>
<span style="color: #bbb;">(</span>contains? @found-primes n<span style="color: #bbb;">)</span>
<span style="color: #E53935;">true</span>
<span style="color: #bbb;">(</span>> @max-prime n<span style="color: #bbb;">)</span>
<span style="color: #E53935;">false</span>
<span style="color: #bbb;">(</span>< @max-prime max-div<span style="color: #bbb;">)</span>
<span style="color: #bbb;">(</span><span style="color: #E53935; font-style: italic;">do</span> <span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">doall</span> <span style="color: #bbb;">(</span>map #<span style="color: #494949;">(</span>is-prime? <span style="font-style: italic;">%</span> <span style="color: #E53935;">true</span><span style="color: #494949;">)</span> <span style="color: #494949;">(</span>range @max-prime max-div<span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">if</span> <span style="color: #bbb;">(</span>div? n<span style="color: #bbb;">)</span>
<span style="color: #bbb;">(</span><span style="color: #E53935; font-style: italic;">do</span> <span style="color: #494949;">(</span>swap! found-primes conj n<span style="color: #494949;">)</span>
<span style="color: #E53935;">true</span><span style="color: #bbb;">)</span>
<span style="color: #E53935;">false</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span>
<span style="color: #bbb;">(</span>div? n<span style="color: #bbb;">)</span>
<span style="color: #bbb;">(</span><span style="color: #E53935; font-style: italic;">do</span> <span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">if</span> contiguous?
<span style="color: #bbb;">(</span><span style="color: #E53935; font-style: italic;">do</span> <span style="color: #494949;">(</span>swap! found-primes conj n<span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>reset! max-prime n<span style="color: #494949;">)</span><span style="color: #bbb;">)</span>
<span style="color: #bbb;">(</span>swap! found-primes conj n<span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
<span style="color: #E53935;">true</span><span style="color: #bbb;">)</span>
<span style="color: #E53935;">:else</span> <span style="color: #E53935;">false</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
</pre>
</div>
<p>
There are, however, a number of fun tricks being used to speed up the computation. First we generate the maximum divisor using this little bit of code. This isn't really the maximum size of the prime divisor, but rather the maximum size of the minimum element of the pair of divisors produced.
</p>
<div class="org-src-container">
<pre class="src src-clojure"><span style="color: #494949;">(</span>int <span style="color: #bbb;">(</span>inc <span style="color: #494949;">(</span><span style="color: #E53935;">Math</span>/sqrt n<span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
</pre>
</div>
<p>
Next we have the conditional. First it checks if the number is in the list of found primes, and if it is then it simply returns <code>true</code>. This means that it has \(O(1)\) runtime should the prime be found already. <label class="sidenote-number" for="3"><sup>3</sup></label><input checked="checked" id="3" style="display:none" type="checkbox" /><span class="sidenote"><span class="sidenote-number"> 3</span> Though in Clojure, since sets are trees, it has more \(O(log(n))\) runtime.</span>
</p>
<div class="org-src-container">
<pre class="src src-clojure"><span style="color: #494949;">(</span>contains? @found-primes n<span style="color: #494949;">)</span>
<span style="color: #E53935;">true</span>
</pre>
</div>
<p>
But, if it is both not in the list of found primes <i>and</i> is less than the largest prime, it must be the case that it is not a prime, and therefore it returns false.
</p>
<div class="org-src-container">
<pre class="src src-clojure"><span style="color: #494949;">(</span>> @max-prime n<span style="color: #494949;">)</span>
<span style="color: #E53935;">false</span>
</pre>
</div>
<p>
Following this we check the case that the <code>max-prime</code> is smaller than <code>max-div</code>. In this case we check the primality of every prime from the last largest prime to the <code>max-div</code>. This places each prime number in the set of found primes and ensures that it can run and check if the number is prime. Following that we check that <code>n</code> is prime.
</p>
<p>
We do add it to the list of primes, but we don't set the <code>max-prime</code>, even though it far exceeds it. This is because the value <code>max-prime</code> represents the maximum prime for which all primes lower than it are known. In this case not all primes lower than it are known.
</p>
<p>
Unfortunately it is not possible to, for any \(n\) know that it is the next prime without testing the range between n and the previous prime. Therefore, for now, this part of it is the only way to check if previous elements are prime.
</p>
<div class="org-src-container">
<pre class="src src-clojure"><span style="color: #494949;">(</span>< @max-prime max-div<span style="color: #494949;">)</span>
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">do</span> <span style="color: #bbb;">(</span><span style="color: #E53935; font-style: italic;">doall</span> <span style="color: #494949;">(</span>map #<span style="color: #bbb;">(</span>is-prime? <span style="font-style: italic;">%</span> <span style="color: #E53935;">true</span><span style="color: #bbb;">)</span> <span style="color: #bbb;">(</span>range @max-prime max-div<span style="color: #bbb;">)</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span>
<span style="color: #bbb;">(</span><span style="color: #E53935; font-style: italic;">if</span> <span style="color: #494949;">(</span>div? n<span style="color: #494949;">)</span>
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">do</span> <span style="color: #bbb;">(</span>swap! found-primes conj n<span style="color: #bbb;">)</span>
<span style="color: #E53935;">true</span><span style="color: #494949;">)</span>
<span style="color: #E53935;">false</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
</pre>
</div>
<p>
Now we check if a number is or is not in fact prime, and in this case we do set the prime in the event it is contiguous because the number is the next number in the set of found primes.
</p>
<div class="org-src-container">
<pre class="src src-clojure"><span style="color: #494949;">(</span>div? n<span style="color: #494949;">)</span>
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">do</span> <span style="color: #bbb;">(</span><span style="color: #E53935; font-style: italic;">if</span> contiguous?
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">do</span> <span style="color: #bbb;">(</span>swap! found-primes conj n<span style="color: #bbb;">)</span>
<span style="color: #bbb;">(</span>reset! max-prime n<span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>swap! found-primes conj n<span style="color: #494949;">)</span><span style="color: #bbb;">)</span>
<span style="color: #E53935;">true</span><span style="color: #494949;">)</span>
</pre>
</div>
<p>
Once we have this function, we can then begin to look into generating the primes to some value. Like before we want to ensure that we can use as many numbers form our prime list as possible, therefore we implement a simple function that will first attempt to return all the values from our <code>found-primes</code> list. should they not exist, it will then use the side effects of the <code>is-prime?</code> function to generate it.
</p>
<div class="org-src-container">
<pre class="src src-clojure"><<divisible?>>
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">defn</span> <span style="font-weight: bold; font-style: italic;">prime-range</span>
<span style="color: #bbb;">(</span><span style="color: #494949;">[</span>end<span style="color: #494949;">]</span> <span style="color: #494949;">(</span>prime-range 2 end<span style="color: #494949;">)</span><span style="color: #bbb;">)</span>
<span style="color: #bbb;">(</span><span style="color: #494949;">[</span>start end<span style="color: #494949;">]</span>
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">if</span> <span style="color: #bbb;">(</span>@max-prime<span style="color: #bbb;">)</span>
<span style="color: #bbb;">(</span>drop-while<span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">->></span> <span style="color: #bbb;">(</span>range <span style="color: #494949;">(</span>max start 2<span style="color: #494949;">)</span> end<span style="color: #bbb;">)</span>
<span style="color: #bbb;">(</span>filter is-prime?<span style="color: #bbb;">)</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">defn</span> <span style="font-weight: bold; font-style: italic;">prime-factors</span> <span style="color: #bbb;">[</span>x<span style="color: #bbb;">]</span>
<span style="color: #bbb;">(</span><span style="color: #E53935; font-style: italic;">->></span> <span style="color: #494949;">(</span>prime-range <span style="color: #bbb;">(</span>inc <span style="color: #494949;">(</span><span style="color: #E53935;">Math</span>/sqrt x<span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>filter #<span style="color: #bbb;">(</span>divisible? x <span style="font-style: italic;">%</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>last <span style="color: #bbb;">(</span>prime-factors 600851475143<span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
</pre>
</div>
</div>
</div>
</div>
</div>
<!-- Footnotes --><!--
<div class="footdef"><sup><a id="fn.1" class="footnum" href="#fnr.1" role="doc-backlink">1</a></sup> <div class="footpara" role="doc-footnote"><p class="footpara">the n-ary function syntax for Clojure is really nice here, allowing me to use default arguments.</p></div></div>
<div class="footdef"><sup><a id="fn.2" class="footnum" href="#fnr.2" role="doc-backlink">2</a></sup> <div class="footpara" role="doc-footnote"><p class="footpara">Even with the <code>recur</code> special form.</p></div></div>
<div class="footdef"><sup><a id="fn.3" class="footnum" href="#fnr.3" role="doc-backlink">3</a></sup> <div class="footpara" role="doc-footnote"><p class="footpara">Though in Clojure, since sets are trees, it has more \(O(log(n))\) runtime.</p></div></div>
--></div>
<div id="postamble" class="status">
<p class="date">Last Modified: 2021-W52-1 00:20</p><p class="creator">Generated Using: <a href="https://www.gnu.org/software/emacs/">Emacs</a> 27.2 (<a href="https://orgmode.org">Org</a> mode 9.4.6)</p><p class="license">Except where otherwise noted content on <a href="https://cons.dev">cons.dev</a> is licensed under a <a href="https://creativecommons.org/licenses/by-sa/4.0/" rel="license">Creative Commons Attribution-ShareAlike 4.0 International License</a>.</p>
</div>
</body>
</html>