Difference between revisions of "Talk:99 questions/Solutions/31"
Latest revision as of 09:15, 8 November 2019
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
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
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"