Sie haben die Bedingungen verwechselt:
divisible x y = ((x `mod` y) /= 0) && not (divisible x (y-1))
sollte sein
divisible x y = (x `mod` y) == 0 || divisible x (y-1)
damit der Test funktioniert.
So wie es ist, Ihr divisible Funktion erweitert z.B.
divisible 21 5 = (21 `mod` 5 /= 0) && not (divisible 21 4)
= (21 `mod` 5 /= 0) && not ((21 `mod` 4 /= 0) && not (divisible 21 3))
= not ((21 `mod` 4 /= 0) && not ((21 `mod` 3 /= 0) && not (divisible 21 2)))
= not (True && not (False && not (divisible 21 3)))
= not (not False)
= False
seit 21 `mod` 3 == 0 y isPrime 21 wertet aus zu True mit der Quadratwurzelgrenze.
Ich bekomme jedoch
*StrangePrime> isPrime 9
True
*StrangePrime> isPrime 13
True
mit Ihrem Code unter Verwendung der Quadratwurzel.
Ohne die Quadratwurzel funktionierte es zufällig für ungerade Zahlen, weil die Differenz zwischen einem ungeraden Kompositum und einem seiner Teiler immer gerade ist. Entfaltung divisible ein paar Schritte für n = p*m donde p ist der kleinste Primfaktor des ungeraden Kompositums n sehen wir
divisible n (n-1) = n `mod` (n-1) /= 0 && not (divisible n (n-2))
= not (divisible n (n-2))
= not (n `mod` (n-2) /= 0 && not (divisible n (n-3)))
= not (not (divisible n (n-3)))
= not^2 (divisible n (n-3))
und induktiv
divisible n (n-1) = not^(k-1) (divisible n (n-k))
wenn es keine Teiler von n größer als n-k . In der obigen Situation ist der größte Teiler von n es m = n - (p-1)*m so erhalten wir
divisible n (n-1) = not^((p-1)*m-1) (divisible n m)
= not^((p-1)*m-1) (n `mod` m /= 0 && not (...))
Pero n `mod` m == 0 Wir haben also
divisible n (n-1) = not^((p-1)*m-1) False
Seit p ist ungerade, p-1 ist gerade, und damit ist auch (p-1)*m , so dass wir insgesamt eine ungerade Anzahl von not s, das entspricht einem not und gibt
divisible n (n-1) = True
isPrime n = not (even n) && not (divisible n (n-1)) = True && not True = False
Si p eine ungerade Primzahl ist, erreicht die Entfaltung divisible p (p-1) = not^(p-3) (divisible p (p - (p-2))) . p-3 gerade ist, divisible p 2 es even p das ist False .
Generell gilt divisible n s für eine ungerade n , und lassen d ist der größte Teiler von n nicht mehr als s si n zusammengesetzt ist, oder d = 2 si n ist primär. Die Entfaltung von divisible n s immer noch auf die gleiche Weise vorgeht
divisible n s = not^k (divisible n (s-k))
solange noch kein Divisor gefunden wurde und s-k > 2 . Im Falle eines zusammengesetzten n finden wir
divisible n s = not^(s-d) (divisible n d)
= not^(s-d) (n `mod` d /= 0 && not (...))
= not^(s-d) False
= odd (s-d)
= even s -- since d is odd, as a divisor of an odd number
und im Falle einer ungeraden Primzahl n ,
divisible n s = not^(s-2) (divisible n 2)
= not^(s-2) (even n)
= not^(s-2) False
= odd s
Así que divisible n s misst die Parität des Abstandes von s auf den nächstkleineren Teiler von n oder auf 2, je nachdem, welcher Wert größer ist. Wenn s war n-1 war der Ausgangspunkt immer gleich, so dass die Berechnung korrekt war, aber ceiling (sqrt (fromIntegral (n-1))) kann ungerade sein. In diesem Fall werden die Ergebnisse umgedreht und Komposita werden zu Primzahlen erklärt und umgekehrt.
Sie können Ihre divisible Funktion für den Primäritätstest von ungeraden Zahlen mit einer Quadratwurzelgrenze funktionieren, wenn Sie sicherstellen, dass der erste Aufruf ein gerades zweites Argument erhält (wenn also ceiling (sqrt (fromIntegral (n-1))) ungerade ist, beginnen Sie bei ceiling (sqrt (fromIntegral (n-1))) + 1 ), aber die Logik dieser Funktion ist verwirrend, und ihr Name beschreibt ihre Ergebnisse nicht korrekt.
Eine idiomatischere Schreibweise wäre
isPrime n = and [n `mod` k /= 0 | k <- [2 .. ceiling (sqrt $ fromIntegral n)]]
Der Test wird effizienter, wenn man Teilerkandidaten überspringt, von denen man bereits aus früheren Tests weiß, dass sie keine Teiler sind, also einfach alle geraden Zahlen außer 2 überspringt,
isPrime 2 = True
isPrime n = all ((/= 0) . (n `mod`)) (2 : [3, 5 .. ceiling (sqrt (fromIntegral n))])
Etwas aufwändiger, aber immer noch effizienter ist auch das Überspringen von Vielfachen von 3
isPrime n = all ((/= 0) . (n `mod`)) (takeWhile (<= bound) (2:3:scanl (+) 5 (cycle [2,4])))
where
bound = ceiling (sqrt (fromIntegral (n-1)))
Auf die gleiche Weise kann man die Vielfachen kleinerer Primzahlen aus den Probedivisoren eliminieren, was jeweils ein wenig Effizienz bringt, aber auf Kosten eines komplizierteren Rads, z. B. führt die Eliminierung der Vielfachen von 5 auch zu
isPrime n = all ((/= 0) . (n `mod`)) (takeWhile (<= bound) (2:3:5: scanl (+) 7 (cycle [4,2,4,2,4,6,2,6])))
where
bound = ceiling (sqrt (fromIntegral (n-1)))
