Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.
share|improve this question

3 Answers 3

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

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?.

share|improve this answer
+1 - Probably the fastest solution available –  eldo Jul 9 at 16:57
@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 –  Artes Jul 9 at 17:12

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]}]

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
{1.857, 12272577818052}
(* in a fresh kernel *)
Total @ Prime @ Range @ PrimePi[2*^7] // Timing
{1.716, 12272577818052}

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

share|improve this answer
First @ NestWhile[
    With[{p = Prime[#[[3]]]}, 
        {#[[1]] + #[[2]], p, #[[3]] + 1}
    ] &,
    {0, 2, 2}, #[[2]] <= 2 10^6 &

EDIT: this is a faster version:

       {Prime@#[[2]], #[[2]] + 1} &,
       {0, 1},
       #[[1]] <= 2 10^6 &][[;;-2, 1]]
share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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