Firstly, let me explain why random generating a prime isn't that bad.

The first reason is the same as blokhead has mentioned, that primes aren't so rare. As he has explained, if you pick a random 31-bit number, it's a prime with 1/21 probability.

The second reason is that even when we don't pick a prime, in most of the cases, it is divisable with a small prime, and in this case, the primality tester algorithm should return false very quickly. Note that even before the R-M test, I divide the number with the first eight primes (this should really be the first 50 primes in real-world applications, but then I wouldn't get much of the R-M algorithm here) first thing I do. Even without those divisions, the R-M test is correct, so they wouldn't strictly be needed, but it really helps finding a random prime number. As a special case, blokhead notes that you can generate a random even number. I do this, but it doesn't help much as the primality tests test the parity of the number anyway. (Update: it was stupid to say that I do this as I haven't posted the code to generate a random prime. Anyway, here it is:

# at that time, primep_rm was called primep, so
sub randprime {
        my $cand;
        do {
                $cand = 10000001 + 2 * int(rand(45000000));
        } until primep($cand);
        $cand;
}
sub randcomposite { # needed for testing
        my $cand;
        do {
                $cand = 10000001 + 2 * int(rand(45000000));
        } until !primep($cand);
        $cand;
}
# ... and the test later ...
if (1) {
        my $F;
        warn "begin";
        open $F, ">", "primes" or die;
        print $F randprime(), "\n" or die for 1 .. 1000;
        close $F or die;
        system q"! factor <primes | cgrep '\d \d'" and die;
        warn "mid";
        open $F, ">", "comps" or die;
        print $F randcomposite(), "\n" or die for 1 .. 1000;
        close $F or die;
        system q"! factor <comps | cgrep -v '\d \d'" and die;
        warn "end";
}
[download]

Now let's look at whether building a table of large primes is feasable, esp as spiritway has asked this too. There are 5 million 8-digit primes, so if we really needed five-digit primes, so we could build a table. However, I'd only do this if you needed five-digit primes very often. (demerphq's original application was a random hash seed, so I don't think he needs it that often.) Also, if you need 9-digit primes or even primes less then 2^31, the table gets larger and larger.