3
$\begingroup$

OK, the problem occurred when I challenged with Project Euler No. 10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million.

My code is:

ClearAll[primelist, i]
primelist = {}; i = 1
While[Prime[i] < 2*10^6, AppendTo[primelist, Prime[i]];i++]
Plus @@ primelist

And I get the answer correct. I think using While is not a good habit in functional programming, but I can not modify my code to NestWhileList(or others FP-like functions). One of the proper manner is:

Plus @@ (Prime /@ NestWhileList[# + 1 &, 1, (Prime[# + 1] < 2*10^6 &)])

But I think it is not efficient, because when evaluating the NestWhileList, Prime[1],Prime[2],Prime[3],... ran the first time(in order to compare with 2*10^6), and then when mapping Prime to the list which was the result of NestWhileList, the same thing went once again! MMA evaluate Prime[1],Prime[2],Prime[3],... one more time.

  1. Is there any method (or SOP) that can always change While to NestWhile or NestWhileList?
  2. And I found that the second code above run faster much more than code 1, unbelievable.
$\endgroup$

3 Answers 3

7
$\begingroup$

When using advanced functionality to deal with primes it is highly recommended not using any of NestList or FoldList or whatever similar.
PrimePi is especially designed to find how many primes are below of a given number, then Prime roughly inverse of PrimePi is Listable, therefore I'd suggest this approach yielding the result almost immediately:

Total @ Prime @ Range @ PrimePi @ 2000000
142913828922  

See closely related Generate PrimePower counting function.
If you are to examine something related to nesting see e.g. this NestList with a list inside?.

$\endgroup$
2
  • $\begingroup$ +1 - Probably the fastest solution available $\endgroup$
    – eldo
    Jul 9, 2014 at 16:57
  • $\begingroup$ @eldo Thanks, when I started to play with Mathematica I used to test something like Select[ range, PrimeQ] just to be convinced that there are better ways, however sometimes one can find another interesting solutions, see e.g. this approach $\endgroup$
    – Artes
    Jul 9, 2014 at 17:12
4
$\begingroup$

I like to use Sum for such things, when possible, as it conserves memory and is usually reasonably fast:

Sum[Prime @ i, {i, PrimePi[2*^6]}]
142913828922

Performance (still in v7, for now...) compared to Artes's fully vectorized code, with a larger search space:

Sum[Prime @ i, {i, PrimePi[2*^7]}] // Timing
MaxMemoryUsed[]
{1.857, 12272577818052}
15904176
(* in a fresh kernel *)
Total @ Prime @ Range @ PrimePi[2*^7] // Timing
MaxMemoryUsed[]
{1.716, 12272577818052}
138293008

So Sum is only slightly slower and uses a fraction of the memory that Total does.


The performance comparison performed in 10.0.2 under Windows:

Sum[Prime @ i, {i, PrimePi[2*^7]}] // Timing
MaxMemoryUsed[]
{2.308815, 12272577818052}

41744320
(* in a fresh kernel *)
Total @ Prime @ Range @ PrimePi[2*^7] // Timing
MaxMemoryUsed[]
{2.199614, 12272577818052}

157160592

Both methods are slower now and use more memory, but Sum remains a good option.

$\endgroup$
2
  • $\begingroup$ i = 0; NestWhile[(++i; # + Prime[i]) &, 0, Prime[i + 1] < 2000000 &] // AbsoluteTiming I just figure out this code! It seems elegant. And it is much more fast than Build-in functions! $\endgroup$
    – Eric
    Aug 9, 2014 at 13:01
  • $\begingroup$ The algorithm is while(Prime[i]<2*10^6){sum=sum+Prime[i]; i++;} $\endgroup$
    – Eric
    Aug 9, 2014 at 13:06
0
$\begingroup$
First @ NestWhile[
    With[{p = Prime[#[[3]]]}, 
        {#[[1]] + #[[2]], p, #[[3]] + 1}
    ] &,
    {0, 2, 2}, #[[2]] <= 2 10^6 &
]

EDIT: this is a faster version:

Total[
   NestWhileList[
       {Prime@#[[2]], #[[2]] + 1} &,
       {0, 1},
       #[[1]] <= 2 10^6 &][[;;-2, 1]]
]
$\endgroup$
3
  • $\begingroup$ I have found a better(not sure) solution based on your second solution. NestWhile[{#[[1]] + Prime[#[[2]]], #[[2]] + 1} &, {0, 1}, Prime[#[[2]]] < 2000000 &] // Timing $\endgroup$
    – Eric
    Aug 9, 2014 at 13:39
  • $\begingroup$ The first entry of the list is recorded as a sum, the second the counter(is going to be the argument of Prime) $\endgroup$
    – Eric
    Aug 9, 2014 at 13:42
  • $\begingroup$ @Eric, my second solution runs a bit faster (in my computer) than your proposal. $\endgroup$
    – ecoxlinux
    Aug 15, 2014 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.