Difference between revisions of "Talk:99 questions/Solutions/31"
From HaskellWiki
Sartorius2 (talk  contribs) (→Wilson's theorem) 
Sartorius2 (talk  contribs) (→Wilson's theorem) 
(No difference)

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
Wilson's theorem
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"