apparently 9.3% of all '5 digit' numbers are prime, so random guessing isn't a bad strategy - you'll find one in 10.75 totally randomly chosen numbers to be prime.
Being a little smarter, prime number can only end in a 1, 3, 7 or 9 - (ending in 0, 2, 4, 6, 8 would be even, ending in 5 would be odd), so in fact it's more like 25% of 'likely' guesses.
IIRC, randomly guessing is _always_ a good strategy for "give me a prime in the range [a, b]" , in other words that's what's used for algorithms that need primes anyway. Either guess and check or guess and increase-by-2-until-prime.
Does work _much_ better in this range than at crypto sizes though.
Being a little smarter, prime number can only end in a 1, 3, 7 or 9 - (ending in 0, 2, 4, 6, 8 would be even, ending in 5 would be odd), so in fact it's more like 25% of 'likely' guesses.