Talk:99 questions/Solutions/31
Revision as of 09:04, 8 November 2019 by Sartorius2 (talk | contribs)
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
Does something as simple but as dump as this should be on the wiki ?
isPrime :: Int -> Bool
isPrime n | n <= 1 = False
isPrime n = isPrime' 2 n
where isPrime' x n | x*x > n = True
| otherwise = (n `rem` x) /= 0 && isPrime' (x+1) n
And something as simple as this one...
isPrime :: Int -> Bool
isPrime n = all (\x -> n `mod`x /= 0) [2..sqr]
where sqr = floor (sqrt (fromIntegral n :: Double))
-- Assuming that a number is not a prime if he is divisible by any number between 2 and his sqrt
Wilson's theorem
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
fact :: Integer -> Integer
fact n
| n == 0 = 1
| otherwise = n * fact (n - 1)
wilsonTest :: Integer -> Bool
wilsonTest p
| f == (p - 1) = True
| otherwise = False
where f = fact (p - 1) `mod` p
"p is prime iff the product of all positive integers less than p is one less than a multiple of p"