这个 Prime-testing 函数有什么问题？

Question

我找遍了几乎所有地方，但找不到以下代码不起作用的原因：

isPrime :: Int -> Bool
isPrime 1 = False
isPrime n = divTest n (floor (sqrt n))
    where
    divTest :: Int -> Int -> Bool
    divTest n test
        | test == 1         = True
        | mod n test == 0   = False
        | otherwise         = divTest n (test-1)

我得到两个错误，它们真的很长，所以我会把我认为重要的部分放在：

No instance for (RealFrac Int) arising from a use of ‘floor’

和

No instance for (Floating Int) arising from a use of ‘sqrt’

是的，我知道这可能效率不高。我在学。

Answer 1

sqrt 需要一个浮点数 - 试试

isPrime n = divTest n (floor (sqrt (fromIntegral  n)))

Answer 2

从 sqrt is of type: Floating a => a -> a, you need to pass a floating point number instead of an integer. You can do this by applying fromIntegral 到 n，如另一个答案所示。

解决此问题的另一种方法是将其分解为两个函数。

第一个函数可以找到最多 n:

的所有因子

factors :: Integer -> [Integer]
factors n = filter divides_n [1..n]
    where divides_n m = n `mod` m == 0

工作原理如下：

*Main> factors 15
[1,3,5,15]

然后我们可以用它来检查一个数是否是素数，如果 factors 只包含 1 和 n:

isPrime :: Integer -> Bool
isPrime n = factors n == [1,n]

按预期工作：

*Main> isPrime 2
True
*Main> isPrime 3
True
*Main> isPrime 4
False
*Main> isPrime 5
True
*Main> isPrime 15
False

这种方法的好处是您无需执行任何棘手的操作来测试数字是否为素数。

Answer 3

另一种计算平方根的方法是计算商和余数，当商小于除数时停止。

-- Work our way up from 3, testing odd divisors only.
divTest :: Int -> Int -> Bool
divTest n test | r == 0 = False
               | q < test = True -- test > sqrt n, and we've tested all the smaller divisors
               | otherwise = divTest n (test + 2)

isPrime :: Int -> Bool
isPrime 1 = False
isPrime 2 = True
isPrime n = n `mod` 2 /= 0 && divTest n 3

这个 Prime-testing 函数有什么问题？

What's wrong with this Prime-testing function?

primes

haskell