<div dir="ltr"><div><span class="Apple-style-span" style="font-family: arial, helvetica, sans-serif;">At the risk of doing someone&#39;s homework...</span></div><div><span class="Apple-style-span" style="font-size: 12px; "><span class="Apple-style-span" style="font-family: arial, helvetica, sans-serif;">A naive solution is to do trial division by all integers from 2 up to sqrt n.</span></span></div>
<div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;"><br class="webkit-block-placeholder"></span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; font-size: 12px;">{-</span></div>
<span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">isPrime :: Integer -&gt; Bool</span><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">isPrime n&nbsp;</span></div>
<div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">&nbsp;| n &lt; 2 &nbsp; &nbsp; = False</span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">&nbsp;| otherwise = f 2 n</span></div>
<div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">&nbsp;where f k n&nbsp;</span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">&nbsp;&nbsp;= if k &gt; isqrt&nbsp;</span></div>
<div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">&nbsp;&nbsp; &nbsp; then True</span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; font-size: 12px;">&nbsp;&nbsp; &nbsp; else undefined -- exercise for the reader</span></div>
<div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">-}</span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;; font-size: 12px;"><br class="webkit-block-placeholder">
</span></div><div><span class="Apple-style-span" style="font-family: arial, helvetica, sans-serif;">and where&nbsp;</span></div><div><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">isqrt n </span><span class="Apple-style-span" style="font-family: arial, helvetica, sans-serif;">returns </span><span class="Apple-style-span" style="font-family: &#39;courier new&#39;, monospace;">floor (sqrt n)</span></div>
<div><br></div><div>Here, f is the helper function, and is only in scope inside the definition of isPrime. This is a common haskell idiom- a helper function that is not quite general purpose enough to be made a standalone function can be defined &quot;on the fly&quot; and doesn&#39;t need a name or type signature.&nbsp;</div>
<div><br class="webkit-block-placeholder"></div><div>You could fancy this up to make it more efficient. I&#39;ve also seen probabilistic functions that can handle huge numbers, but I can&#39;t remember if they are recursive.</div>
</div>