It's common in math to get theorems that prove existence without giving any explicit examples (nonconstructive proofs). A big research area is coming up with efficient ways to construct such examples.

Definitely true, but these things are of a different "kind" (in my opinion). Often such a proof implies, for instance, a really inefficient algorithm, such as "try all the random possibilities and with positive probability such an example exists. They also tend to have a flavor of a somewhat complicated object whose existence you are proving, and they don't tend to be phrased as algorithms (especially not efficient ones).

Here the primality test algorithm is an efficient algorithm, and doesn't seem natural to view as an existence/nonexistence proof of an object, in the same way. Instead it's exploiting the number-theoretic properties of primality in a weird way. Hope that makes sense, but anyway just trying to explain my intuition for why this is very different from the phenomenon you mentioned.