it's fairly apparent that Anonymous Monk was thinking of getting a list of prime numbers, putting them in a flat text file, and reading that file into memory whenever the list of primes is needed.

Actually, that can be even faster than my lookup version. Provided that you store them in a fixed record format file--binary or ascii--then getting the Nth prime is just a seek and small read away.

The following uses a simple flat ascii file with the primes padded to 9 bytes (+CRLF). Lookup times for individual primes are consistantly under half a millisecond:

C:\test>primes-a 2
        3

Took: 0.000457048416137695 seconds

C:\test>primes-a 15e6
275604541

Took: 0.000396966934204102 seconds

C:\test>primes-a 12345678
224284387

Took: 0.000416040420532227 seconds
[download]

Teh downside is the size of the datafile:

C:\test>dir data\primes.all
2006-02-04  15:50       165,000,000 primes.all
[download]

The program:

#! perl -slw
use strict;
use Time::HiRes qw[time];;

my $start = time;

open P, '<:raw', 'data\primes.all';
seek P, 11 * ( $ARGV[ 0 ] - 1 ), 0;
print scalar <P>;
close P;

print "Took: ", time() - $start, ' seconds';;
[download]