That doesn't quite generate a prime. It generates a number that's a prime with a very high probability. There's always a small chance that it's not prime but it's good enough given the tradeoffs needed to verify that it's prime with 100% certainty.

Yeah, sorry perhaps I shouldn't have made such a specific sounding claim. I'm not an expert on this topic, but was pretty sure I had heard from reputable sources in the past that the Riemann Hypothesis had some bearing on the distribution of prime numbers. And it feels safe to say that this could have practical implications for cryptography. But maybe I should just leave it to the experts :).