It is very very difficult to construct large prime numbers for exactly the reasons you have pointed out. That is precisely the reason we use the RSA code to encrypt things. If you did have a very good way to generate large prime numbers I would guess the NSA would like to talk to you very badly.

I was a member of one of those distributive computing projects that helped search for large primes of the form called Riesel Sieve Project. I am not sure if it still exists or not, I got a new computer and never got around to reinstalling it.