The fastest way would be to use a table.

my @primes = (2, 3, 5, 7, 11, 13, 17, 19);

sub get_a_prime {
   return $primes[rand @primes];
}

sub get_primes_iter {
   my $i = 0;
   return sub {
      return if $i > $#primes;
      return $primes[$i++];
   };
}

print(get_a_prime(), "\n");

my $i = get_primes_iter();
while (my ($prime) = $i->()) {
   print("$prime\n");
}
[download]

Or do you have a more specific criteria?