测试整数是否为素数

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这一点。测试整数是否为素数

来源

2017-04-23 user3358850

这里它使用了一个事实，即整数的最小素因子是2，所以最大可以是至多n/2。

更好的算法将检查最多sqrt（n）的数字，以查找是否存在因子。

像这样

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

虽然你需要处理1作为一个特殊的情况下，非黄金

UPDATE

短路的sqrt（N）之间的支票到n对于素数，这可能是更好的方法

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

来源

2017-04-23 02:14:39 karakfa

这不是最好的方法来检查只有平方根，因为它必须通过循环'2..n'并反复立即丢弃'sqrt n..n'中的每个数字。抛弃所有这些数字需要很长时间。问题中的代码只处理这个数字的一半。 –

是的，右侧添加了更好的过滤版本。 – karakfa

测试整数是否为素数

回答

相关问题