Well, you could create a simple sieve that finds all primes between less than 500 (or just use brute force - square root of 500 is less than 23, and you'll know the primes up to 23 I presume), and use them.

But that sounds like too much work to me. It's only worthwhile to use really efficient prime searching algorithms if the numbers involved are much bigger than what a Perl integer can hold.