CODEWITHSUNDEEP
haskell
user2424276
user2424276

Reputation: 611

Primality test in Haskell

I have the following code in Haskell. I want to repeat 30 times the Fermat primality test for a given number n, but the problem is that it always returns False...I tried to fix the problem but I always get wrong answers..Any ideas?

import System.Random
import System.IO.Unsafe

takeARandomNum n=unsafePerformIO (getStdRandom (randomR (2,n)))

fermatTestA :: (Int, Int) -> Bool
fermatTestA (n, a) =((a^(n-1) `mod` n)==1)

solve :: (Int, Int) -> Bool
solve (n, 1) = fermatTestA (n, takeARandomNum (n-2))
solve (n, maxTest)
    | fermatTestA (n, takeARandomNum (n-2)) = (solve (n, (maxTest-1)))
    | otherwise = False

fermatTest :: Int ->Bool
fermatTest n = solve (n, 30)

Upvotes: 1

Views: 453

Answers (1)

svk
svk

Reputation: 5919

Your integers are getting truncated. "Int" in Haskell is not the big-integer type. Change all your "Int" type declarations to "Integer" and your code should work.

Upvotes: 5

Related Questions