0

我已经实现了以下两个函数来确定 n 是否是 fermat 素数（如果它为真则返回 n，如果不是则返回 -1），但它总是返回 -1，无法弄清楚为什么（gc 是一个函数 taht 计算gcd)

fermatPT :: Int -> Int
fermatPT n = fermatPT' n list
  where
    list = [a | a <- [1..n-1]]

-- | heper function
fermatPT' :: Int -> [Int] -> Int
fermatPT' n l      | gc (n, head l) == 1 && fermatTest n (head l) = fermatPT' n (tail l)
                   | null l                                       = n
                   | otherwise                                    = -1
                where
                  fermatTest n a = mod (a^(n-1)) n == 1
4

1 回答 1

2

您的函数应返回一个布尔值，指示给定数字是否为素数。如果这样做，您可以使用该all函数将其简单地定义为

fermatPT :: Integer -> Bool
fermatPT n = all (fermatTest n) (filter (\a -> gcd n a == 1) [1..n-1])
             where fermatTest n a = mod (a^(n-1)) n == 1

gcd在 Prelude 中定义。

all避免需要您一次将测试应用于一个元素的显式递归[1..n-1]；它的定义是有效的

all _ [] = True
all p (x:xs) = p x && all p xs

请注意，这mod (a ^ (n - 1)) n是低效的，因为在最终将其减少到 range 之前，它可能需要计算一个大得离谱的数字[0..n-1]。相反，利用ab mod n == (a mod n * b mod n) mod n, 并在每次乘法后减少值。实现这一点的一种方法（不是最快的，但很简单）：

modN :: Integer -> Integer -> Integer -> Integer
modN a 0 _ = 1
modN a b n = ((a `mod` n) * (modN a (b - 1) n)) `mod` n

然后使用

fermatTest n a = modN a (n-1) n == 1

请注意，您可以使用它（用Int而不是Integer）来正确实现fermatPT :: Int -> Bool; 尽管输入仍将被限制为较小的整数，但它不会出现溢出。

于 2017-12-05T16:52:16.750 回答