Okay. Since none of the math guys have answered, I'll risk telling you my uninformed opinion on the matter. As far as I am aware:

1. The most efficient way of generating 'small' primes, defined as < 1e10, is the Sieve of Atkins, which is a kind of variation on the the Sieve of Eratosthenes that uses quadratic forms. I read that. I don't know what it means :)

   For this to be efficient for time requires it to be coded in platform specific C (with masses of performance critical bit twiddling), or hand crafted assembler that also requires intimite knowledge of the performance characteristics of the cpu used.

   There is also a method known as 'wheel factorisation', but again, you cannot predict how high you would need to go before you will find the N you want. It has the advantage of not requiring the retention of the list of primes so far, but requires more divsions and so is generally slower.

2. As with the SoE, there is no exact method of knowing how high to go with the SoA in order to generate the first N primes.

   The best you can do is set your upper bound to N log N where N is the number you wish to find. This approximation apparently tends to get more accurate the higher you go?

You could download a good implementation that will generate the list very quickly. Once you've generated the list once, the lookup method is probably quicker.

You could maybe make it quicker still by storing the list in packed binary. You'd only need a 60 MB file instead of 160 MB, and would read less. unpacking to an array may be quicker than conversion from ascii.

For my purposes a while back, I wanted the nearest prime less than a number within the program, so a binary chop lookup with a resonable guess at starting position worked best for me.

I had a go myself to see what was possible with simple code. It doesn't scale well, but is acceptable for the first 100,000 primes.

---

DWIM is Perl's answer to Gödel

I just saw that and decided to time the mechanism I suggested. At 1/3rd of a second for the first million, it even surprised me :)

#! perl -slw
use strict;
use Devel::Timer;

my $T = new Devel::Timer;

sub firstNprimes {
    my $n = shift;
    open my $primes, '<:raw', 'primes.all' or die $!;
    my @primes = split ' ', do{ local $/ = \( $n * 10 ); <$primes> };
    close $primes;
    return \@primes;
}

$T->mark( '201' );
my $ref1 = firstNprimes( 201 );

$T->mark( '100,000' );
my $ref2 = firstNprimes( 100_000 );

$T->mark( '1,000,000' );
my $ref3 = firstNprimes( 1_000_000 );

$T->report;
__END__
C:\Perl\test\data>..\junk4



Devel::Timer Report -- Total time: 0.3176 secs

Interval  Time    Percent

----------------------------------------------

02 -> 03  0.3169  99.78%  100,000 -> 1,000,000

01 -> 02  0.0007   0.21%  201 -> 100,000

00 -> 01  0.0000   0.01%  INIT -> 201
[download]

That's the ascii version, and it does slow down quite quickly due memory allocation as you go larger; 2 million takes 8 seconds.

I might try the binary file version later.

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.