blob: 9c321ca6c39ac778ff43c99ef854a8dfc6830b69 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
import System.Random
isPrime :: Integral a => a -> Bool
isPrime x = and $ fmap ((/=0).(mod x)) [2..(x-1)]
testn = 10
isPrimeT 2 = True
isPrimeT x = and $ fmap ((/=0).(fstPow x (x-1))) $ take testn $ randomRs (2,(x-1)) (mkStdGen 100)
fstPow _ 1 x = x
fstPow m y x
| y `mod` 2 == 1 = (x * (fstPow m (y `div` 2) (sqr x))) `mod` m
| otherwise = fstPow m (y `div` 2) (sqr x)
where sqr a = (a*a) `mod` m
|
