Comment by mateo1

Besides, when you're just looking for a prime, you can spot things that look like a prime and test them deterministically.