First n primes

Questions
1

Hi,
Is there a “best practices” way to generate the first n primes? Two ways immediately spring to mind:

Select[Range[n],PrimeQ]

Prime[Range[PrimePi[n]]]

According to my internal picture of “what good Mathematica looks like”, the last one is a whole lot more likely to be faster. However, in real life, it’s not. The first option is considerably quicker, although it does use a bit more memory.
Given the ease of sieving for primes, I’d have thought there would be a better way to do this. Is there a correct way to specify the problem so that Mathematica knows to just return the output of a sieve, rather than having to deal with each prime in turn?

EDITED the first example was erroneously written as Select[Range[PrimePi@n], PrimeQ]

2

@Patrick, actually these two code does not produce same result. Please try n =10000

primes.PNG
primes.PNG1372×710 60.6 KB

3 
p = Table[Prime[n],{n,#}] &;

p @ 10000

basically copied from the Prime help page seems to be simple and fast.

4

@Shenghui - thanks, I didn’t mean to put the extra PrimePi into the first one (which you evaluated second).
@Steven - it’s not as fast as Prime@Range@PrimePi is - presumably because Prime is Listable. The millionth prime is 15485863:

In[35]:= Prime[Range[PrimePi[15485863]]]; // AbsoluteTiming
Out[35]= {4.762213, Null}

In[38]:= p[1000000]; // AbsoluteTiming
Out[38]= {5.087068, Null}

These results are the same when the system cache is cleared in between.

5

It looks like these two methods actually take the same amount of time (on average) to compute.

In[1]:= p = Table[Prime[n], {n, #}] &;

In[2]:= a = Table[
{n, First[Timing[Prime[Range[PrimePi[n]]]]]}, 
{n, 1000000, 10000000, 500000}];

In[3]:= b = Table[
{n, First[Timing[p[PrimePi[n]]]]}, 
{n, 1000000, 10000000, 500000}];

In[4]:= ListLinePlot[{a, b}]

360×228 2.86 KB

EDIT: After a bit more testing, it does seem like Prime[Range[PrimePi]] is slightly faster, but they seem close enough so that the decision could be made based on personal preference.

am = Mean[Table[
    {n, First[Timing[Prime[Range[PrimePi[n]]]]]},
    {50},
    {n, 1000000, 10000000, 2000000}]
   ];

bm = Mean[Table[
    {n, First[Timing[p[PrimePi[n]]]]},
    {50},
    {n, 1000000, 10000000, 2000000}]
   ];

ListLinePlot[{am, bm}]

Untitled-3.png
Untitled-3.png360×230 2.72 KB

6

Just FYI: Using NextPrime iteratively is really bad choice. I just tried, 6-7 times slower than either of the other two methods.

7

I just use

Prime[Range[n]]

to generate n primes, here are some timeings as comparison.

k = Prime[Range[1000000]]; // AbsoluteTiming
{1.6536029, Null}

l = Prime[Range[PrimePi[15485863]]]; // AbsoluteTiming
{1.653603, Null}

Paul.