Small nitpick, finding/generating primes is already very efficient/easy, e.g. if you want a 1000-digit prime, then in that range about one in every 2300 is prim

Small nitpick, finding/generating primes is already very efficient/easy, e.g. if you want a 1000-digit prime, then in that range about one in every 2300 is prime (by standard heuristics based on the prime number theorem), so if you try a few thousand random numbers and test them for primality (which is fast too), you'll have found a prime with high probability -- and this is even without trying to avoid obviously non-prime numbers like multiples of 2 or 3. What is hard is factoring, i.e. finding the precise two primes p and q that were multiplied to result in pq. (In fact RSA relies on being able to pick two random primes easily, but which are hard to recover from their product.)