algorithm - 测试整数是否为质数

isPrime::Integer->Bool
isPrime n=not (hasfactor n 2(div n 2))

hasfactor::Integer->Integer->Integer->Bool
hasfactor n low high
    |low>high=False
    |mod n low==0=True
    |otherwise = hasfactor n (low+1) high

我理解大部分代码，除了第二行，not (hasfactor n 2(div n 2))为什么上界是(div n 2)？
假设我们test 8，那么(hasfactor n 2(div n 2))就是hasfactor 8 2 4，这里看不到划分8的点。

最佳答案

这里使用的事实是一个整数的最小素因子是2，所以最大的最多可以是n/2。
一个更好的算法将检查sqrt（n）以内的数字，以确定是否存在因子。
像这样的东西

prime n = null [ k | k <- [2..n], k*k <= n, mod n k == 0 ]

尽管你需要把1作为一种特殊情况处理为非素数
更新
为了使sqrt（n）到n之间的质数检查短路，这可能是一个更好的方法

prime n = null [ k | k <- takeWhile (\x -> x*x<=n) [2..], mod n k == 0 ]

关于algorithm - 测试整数是否为质数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43566635/