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

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

share|improve this answer
    
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! –  Eric Aug 9 at 13:01
    
The algorithm is while(Prime[i]<2*10^6){sum=sum+Prime[i]; i++;} –  Eric Aug 9 at 13:06
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]]
]
share|improve this answer
    
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 –  Eric Aug 9 at 13:39
    
The first entry of the list is recorded as a sum, the second the counter(is going to be the argument of Prime) –  Eric Aug 9 at 13:42
    
@Eric, my second solution runs a bit faster (in my computer) than your proposal. –  ecoxlinux Aug 15 at 16:06

Your Answer

 
discard

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.