https://wiki.haskell.org/api.php?action=feedcontributions&user=Sartorius2&feedformat=atomHaskellWiki - User contributions [en]2020-04-01T22:06:33ZUser contributionsMediaWiki 1.27.4https://wiki.haskell.org/index.php?title=Talk:99_questions/Solutions/31&diff=63116Talk:99 questions/Solutions/312019-11-08T09:15:20Z<p>Sartorius2: /* Wilson's theorem */</p>
<hr />
<div>Does something as simple but as dump as this should be on the wiki ?<br />
<haskell><br />
isPrime :: Int -> Bool<br />
isPrime n | n <= 1 = False<br />
isPrime n = isPrime' 2 n<br />
where isPrime' x n | x*x > n = True<br />
| otherwise = (n `rem` x) /= 0 && isPrime' (x+1) n<br />
</haskell><br />
<br />
== And something as simple as this one... ==<br />
<br />
<haskell><br />
isPrime :: Int -> Bool<br />
isPrime n = all (\x -> n `mod`x /= 0) [2..sqr]<br />
where sqr = floor (sqrt (fromIntegral n :: Double))<br />
</haskell><br />
-- Assuming that a number is not a prime if he is divisible by any number between 2 and his sqrt<br />
<br />
== Wilson's theorem ==<br />
<br />
While the square root test is nice and quick, I do believe Wilson's theorem is much more mathematically elegant since it doesn't rely on the knowledge of other primes, even if it is rather slow because of the factorial<br />
<haskell><br />
fact :: Integer -> Integer<br />
fact n<br />
| n == 0 = 1<br />
| otherwise = n * fact (n - 1)<br />
<br />
wilsonTest :: Integer -> Bool<br />
wilsonTest p<br />
| f == (p - 1) = True<br />
| otherwise = False<br />
where f = fact (p - 1) `mod` p<br />
</haskell><br />
"''p'' is prime iff the product of all positive integers less than ''p'' is one less than a multiple of ''p''"</div>Sartorius2https://wiki.haskell.org/index.php?title=Talk:99_questions/Solutions/31&diff=63115Talk:99 questions/Solutions/312019-11-08T09:04:01Z<p>Sartorius2: </p>
<hr />
<div>Does something as simple but as dump as this should be on the wiki ?<br />
<haskell><br />
isPrime :: Int -> Bool<br />
isPrime n | n <= 1 = False<br />
isPrime n = isPrime' 2 n<br />
where isPrime' x n | x*x > n = True<br />
| otherwise = (n `rem` x) /= 0 && isPrime' (x+1) n<br />
</haskell><br />
<br />
== And something as simple as this one... ==<br />
<br />
<haskell><br />
isPrime :: Int -> Bool<br />
isPrime n = all (\x -> n `mod`x /= 0) [2..sqr]<br />
where sqr = floor (sqrt (fromIntegral n :: Double))<br />
</haskell><br />
-- Assuming that a number is not a prime if he is divisible by any number between 2 and his sqrt<br />
<br />
== Wilson's theorem ==<br />
<br />
While the square root test is nice and quick, I do believe Wilson's theorem is much more mathematically elegant, even if it is rather slow because of the factorial<br />
<haskell><br />
fact :: Integer -> Integer<br />
fact n<br />
| n == 0 = 1<br />
| otherwise = n * fact (n - 1)<br />
<br />
wilsonTest :: Integer -> Bool<br />
wilsonTest p<br />
| f == (p - 1) = True<br />
| otherwise = False<br />
where f = fact (p - 1) `mod` p<br />
</haskell><br />
"''p'' is prime iff the product of all positive integers less than ''p'' is one less than a multiple of ''p''"</div>Sartorius2