<div dir="ltr"><div><span class="Apple-style-span" style="font-family: arial, helvetica, sans-serif;">At the risk of doing someone'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: 'courier new', monospace;"><br class="webkit-block-placeholder"></span></div><div><span class="Apple-style-span" style="font-family: 'courier new'; font-size: 12px;">{-</span></div>
<span class="Apple-style-span" style="font-family: 'courier new', monospace;">isPrime :: Integer -> Bool</span><div><span class="Apple-style-span" style="font-family: 'courier new', monospace;">isPrime n </span></div>
<div><span class="Apple-style-span" style="font-family: 'courier new', monospace;"> | n < 2 = False</span></div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace;"> | otherwise = f 2 n</span></div>
<div><span class="Apple-style-span" style="font-family: 'courier new', monospace;"> where f k n </span></div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace;"> = if k > isqrt </span></div>
<div><span class="Apple-style-span" style="font-family: 'courier new', monospace;"> then True</span></div><div><span class="Apple-style-span" style="font-family: 'courier new'; font-size: 12px;"> else undefined -- exercise for the reader</span></div>
<div><span class="Apple-style-span" style="font-family: 'courier new', monospace;">-}</span></div><div><span class="Apple-style-span" style="font-family: 'courier new'; 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 </span></div><div><span class="Apple-style-span" style="font-family: 'courier new', 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: 'courier new', 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 "on the fly" and doesn't need a name or type signature. </div>
<div><br class="webkit-block-placeholder"></div><div>You could fancy this up to make it more efficient. I've also seen probabilistic functions that can handle huge numbers, but I can't remember if they are recursive.</div>
</div>