Sprawdź, czy liczba całkowita jest liczbą pierwszą - algorytm, haskell

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

Rozumiem większość kodu, z wyjątkiem drugiej linii, not (hasfactor n 2(div n 2)). Dlaczego wyższa granica (div n 2)? Powiedz, jeśli my test 8, następnie (hasfactor n 2(div n 2)) jest hasfactor 8 2 4, Nie widzę punktu podziału 8 tutaj.

Odpowiedzi:

tutaj używa się faktu, że najmniejszy czynnik pierwotny liczby całkowitej to 2, więc największy może być najwyżej n / 2.

Lepszy algorytm sprawdza liczby do sqrt (n), aby ustalić, czy istnieje czynnik, czy nie.

coś takiego

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

choć musisz sobie z tym poradzić 1 jako specjalny przypadek jako non prim

AKTUALIZACJA

w celu sprawdzenia między sqrt (n) a n dla liczb pierwszych, może to być lepsze podejście

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