Difference between revisions of "Talk:99 questions/Solutions/31"

From HaskellWiki
Jump to: navigation, search
(Wilson's theorem)
 
(One intermediate revision by the same user not shown)
Line 16: Line 16:
 
</haskell>
 
</haskell>
 
-- Assuming that a number is not a prime if he is divisible by any number between 2 and his sqrt
 
-- 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
  +
<haskell>
  +
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
  +
</haskell>
  +
"''p'' is prime iff the product of all positive integers less than ''p'' is one less than a multiple of ''p''"

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"