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

From HaskellWiki

Sartorius2 (talk | contribs) (→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*"