Not sure what you mean by "trivial", I mean a simple prime finding algorithm is easy to write down, but it will be very inefficient, especially for large primes (the very ones you use in cryptography).

Coming up with an efficient prime-finding algorithm like Miller-Rabin* is far from trivial.

* Technically it's just a prime-checking algorithm, but you can just generate random numbers until you've verified one of them is prime.