If this isn't quick enough, I do have the binary version I mentioned somewhere.

Update: Found it.

The following shows the code finding the 15 millionth prime in 47 milliseconds, and producing the full list of the first 15 million in 12 seconds.

C:\test>primes.pl 15e6
The 15000000th prime is: 275604541
1 trial of Finding the 15000000 prime (47.118ms total)

1 trial of Retrieving the first 15000000 primes (11.906s total)
[download]

It requires 15 MB of disk storage, and 15 MB of ram if you only want to retrieve them individually. It takes ~600 MB to expand the full list in memory. This is the code and benchmark:

#! perl -slw
use strict;

package primes;

open my $fh, '<:raw', 'data\primes.deltas.bin' or die $!;
read( $fh, my( $deltas ), -s( 'data\primes.deltas.bin' ) );
close $fh;

sub firstNprimes {
    my( $n ) = @_;
    my @primes = unpack 'C*', $deltas;
    $primes[ $_ ] += $primes[ $_ - 1 ] for 1 .. $#primes;
    return \@primes;
}

sub primeN { return unpack "%32C$_[0]", $deltas; }


package main;
use Benchmark::Timer;
die 'Supply N' unless @ARGV;

$ARGV[ 0 ] +=0; ## force numeric

my $T = new Benchmark::Timer;

$T->start( "Finding the $ARGV[ 0 ] prime" );
print "The $ARGV[ 0 ]th prime is: ",  primes::primeN( $ARGV[ 0 ] );
$T->stop( "Finding the $ARGV[ 0 ] prime" );

$T->start( "Retrieving the first $ARGV[ 0 ] primes" );
my $primes = primes::firstNprimes( $ARGV[0] );
$T->stop( "Retrieving the first $ARGV[ 0 ] primes" );
$T->report;

print "The first 100 primes are:";
print for @{ $primes }[ 0 .. 99 ];
print "The last  100 primes (of the first ARGV[ 0 ]) are:";
print for @{ $primes }[ -100 .. -1 ];
[download]

The file, data\primes.deltas.bin above is produced by downloading the 160 MB list from here, and manipulating it to reduce the storage requirement. I achieved the reduction by noting that the delta between successive primes is always less than 255 (for the first 15 million), and so can be stored as a single byte.

To retrieve any individual prime, it is simply a process of summing the first N deltas. This would be rather slow using perl were it not for the little used feature of unpack which can calculate checksums of a string of binary data very quickly. To calculate the 32-bit checksum of a string of bytes, you use

$checksum = unpack '%32C*', $bytes;
[download]

Hence, the primeN() function simply becomes

sub primeN { return unpack "%32C" . (0+$_[0]), $deltas; }
[download]

And runs amazingly quickly, taking around N*3 microseconds, though the cost of the function call swamps the generation time until you reach 100,000 or so.