I’m dabbling with ocaml (once again) and use Project Euler as a playground.
Since I might happen upon “large” numbers while poking the problems, I am using zarith.
The documentation on zarith 1.13 (latest) · OCaml Package states:
Returns the next prime greater than the argument. The result is only prime with very high probability.
I understand that Z.nextPrime is really Z.next_probable_prime. I could not find more details about the “next” part, though: Is it possible for Z.nextprime to miss primes? If so, does anybody know what the smallest missed prime would be?
Curious,
s.
Z.nextPrime internally calls out[1] to mpz_nextprime[2] which internally just increments up from your current number until it finds a number that passes the Miller-Rabin probabilistic primailty check.
The relevant property of the Miller Rabin test here is that it will never produce a false negative – if it returns false (that is, states that a number is not prime), then due to how the test works, that number must be composite. (There is, on the other hand, a chance of false positives, where it may state that a result is prime when it is in fact composite).
Anyway, this means that nextprime will never miss primes. It may return “early” in its search and produce a value that is not-prime, but in that case, you can be certain that this value is smaller than the next prime.
[1] Zarith/caml_z.c at 0083fbd986570a2906461a83ab68b6823466fcc7 · ocaml/Zarith · GitHub
[2] GMP/nextprime.c at 2bbd52703e5af82509773264bfbd20ff8464804f · alisw/GMP · GitHub
2 Likes
Thank you for confirming my suspicions. My math and C skills have gotten rusty over the years 