0
|
8225 Views
|
6 Replies
|
3 Total Likes
View groups...
Share
GROUPS:

First n primes

Posted 12 years ago
 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 12 years ago
 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}]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 12 years ago
 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.
Posted 12 years ago
 @Patrick, actually these two code does not produce same result. Please try n =10000
Posted 12 years ago
 p = Table[Prime[n],{n,#}] &;p @ 10000 basically copied from the Prime help page seems to be simple and fast.
Posted 12 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[35]:= Prime[Range[PrimePi[15485863]]]; // AbsoluteTimingOut[35]= {4.762213, Null}In[38]:= p[1000000]; // AbsoluteTimingOut[38]= {5.087068, Null}These results are the same when the system cache is cleared in between.
Posted 12 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.