測試整數是否爲素數

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

測試整數是否爲素數

回答

相關問題