# First n primes

Posted 10 years ago
6721 Views
|
6 Replies
|
3 Total Likes
|
 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]
6 Replies
Sort By:
Posted 10 years ago
 I just use Prime[Range[n]]to generate n primes, here are some timeings as comparison.k = Prime[Range]; // AbsoluteTiming{1.6536029, Null}l = Prime[Range[PrimePi]]; // AbsoluteTiming{1.653603, Null}Paul.
Posted 10 years ago
 Just FYI: Using NextPrime iteratively is really bad choice. I just tried, 6-7 times slower than either of the other two methods.
Posted 10 years ago
 It looks like these two methods actually take the same amount of time (on average) to compute. In:= p = Table[Prime[n], {n, #}] &;  In:= a = Table[ {n, First[Timing[Prime[Range[PrimePi[n]]]]]},  {n, 1000000, 10000000, 500000}];  In:= b = Table[ {n, First[Timing[p[PrimePi[n]]]]},  {n, 1000000, 10000000, 500000}];In:= ListLinePlot[{a, b}] 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}] Posted 10 years ago
 p = Table[Prime[n],{n,#}] &;p @ 10000 basically copied from the Prime help page seems to be simple and fast.
Posted 10 years ago
 @Patrick, actually these two code does not produce same result. Please try n =10000 Posted 10 years ago
 @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:= Prime[Range[PrimePi]]; // AbsoluteTimingOut= {4.762213, Null}In:= p; // AbsoluteTimingOut= {5.087068, Null}These results are the same when the system cache is cleared in between.