Re: Math help: Finding Prime Numbers (Updated with code)

[BrowserUk]

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)

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 ];

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;

Hence, the primeN() function simply becomes

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

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.