Thanks. :)

The most surprising thing is surely that the "sum" part is O(n + log n) (so O(n) too, after all) and that this is faster than the simple sum through a loop with a break statment in O(n) ;)

For the prime generation, the memoiazation is the key...