## The Sum Of The First Billion Primes

### September 11, 2012

We start by noting that there is no formula for computing the sum of a set of prime numbers; you have to enumerate each prime and add them up. We also note that the billionth prime is 22801763489, which we can calculate using the algorithm of a previous exercise, so whatever algorithm we use for generating the primes, we should be prepared for a long-running program. We will develop several different functions for generating primes and use this generic calling function for testing:

`(define (sum-primes gen n)`

(let loop ((p (gen)) (n n) (s 0))

(if (zero? n) s

(loop (gen) (- n 1) (+ s p)))))

Our first generator uses brute force; generate all the integers starting from 2, and test each for primality using trial division. For small generators, say several thousand primes, this is hard to beat:

`(define (gen-brute)`

(define (prime? n)

(if (even? n) (= n 2)

(let loop ((d 3))

(cond ((< n (* d d)) #t)

((zero? (modulo n d)) #f)

(else (loop (+ d 2)))))))

(let ((next 2))

(lambda ()

(let loop ((n (+ next 1)))

(if (prime? n)

(let ((p next))

(set! next n)

p)

(loop (+ n 1)))))))

We time the function like this:

`> (time (sum-primes (gen-brute) 1000000))`

(time (sum-primes (gen-brute) ...))

157 collections

132289 ms elapsed cpu time, including 15 ms collecting

132341 ms elapsed real time, including 10 ms collecting

1323026560 bytes allocated, including 1322982416 bytes reclaimed

7472966967499

Our second generator also loops over numbers, testing each for primality, but both the list of numbers and the primality test are improved from the brute-force generator. We generate candidate primes using a 2,3,5,7-wheel, which greatly reduces the number of candidates. We test primality using strong pseudoprime tests to bases 2, 7 and 61, which limits the generator to 32-bit primes; that means we won’t be able to sum the first billion primes, but it is suitable for smaller generators, and because this generator is faster than the previous one (except over small ranges), has compact code, and uses only a small, constant amount of space, it is the generator of choice for many applications:

`(define (gen-wheel)`

(define (prime? n) ; n < 2^32

(define (expm b e m)

(define (times x y) (modulo (* x y) m))

(let loop ((b b) (e e) (r 1))

(if (zero? e) r

(loop (times b b) (quotient e 2)

(if (odd? e) (times b r) r)))))

(define (witness? a n) ; composite if #t

(do ((d (- n 1) (/ d 2)) (s 0 (+ s 1)))

((odd? d)

(let ((t (expm a d n)))

(if (or (= t 1) (= t (- n 1))) #f

(do ((s (- s 1) (- s 1))

(t (expm t 2 n) (expm t 2 n)))

((or (zero? s) (= t (- n 1)))

(zero? s))))))))

(cond ((zero? (modulo n 2)) (= n 2))

((zero? (modulo n 7)) (= n 7))

((zero? (modulo n 61)) (= n 61))

(else (not (or (witness? 2 n)

(witness? 7 n) (witness? 61 n))))))

(let ((wheel (cons 1 (cons 2 (cons 2 (cons 4

(let ((xs (list 2 4 2 4 6 2 6 4 2 4 6 6 2 6

4 2 6 4 6 8 4 2 4 2 4 8 6 4 6 2 4 6

2 6 6 4 2 4 6 2 6 4 2 4 2 10 2 10)))

(set-cdr! (last-pair xs) xs) xs))))))

(next 2))

(lambda ()

(let loop ((n (+ next (car wheel))))

(set! wheel (cdr wheel))

(if (not (prime? n)) (loop (+ n (car wheel)))

(let ((result next)) (set! next n) result))))))

Here’s our timing test, which shows that the wheel is between four and five times faster than brute force:

`> (time (sum-primes (gen-wheel) 1000000))`

(time (sum-primes (gen-wheel) ...))

464 collections

28891 ms elapsed cpu time, including 16 ms collecting

28882 ms elapsed real time, including 30 ms collecting

3912633392 bytes allocated, including 3907682192 bytes reclaimed

7472966967499

Our third generator is based on a variant of the Sieve of Eratosthenes due to Melissa O’Neill; we studied it in a previous exercise. The idea is to keep a priority queue of the next multiple of each prime seen so far; each odd number in order becomes a candidate prime, the current candidate is declared prime if it is not at the head of the priority queue and a new sieving prime is added to the priority queue, but the current candidate is declared composite if it is found at the head of the priority queue and it replaced by its next multiple:

`(define (gen-oneill)`

(define (pq-rank pq) (vector-ref pq 0))

(define (pq-item pq) (vector-ref pq 1))

(define (pq-lkid pq) (vector-ref pq 2))

(define (pq-rkid pq) (vector-ref pq 3))

(define pq-empty (vector 0 'pq-empty 'pq-empty 'pq-empty))

(define (pq-empty? pq) (eqv? pq pq-empty))

(define (pq-merge lt? p1 p2)

(define (pq-swap item lkid rkid)

(if (< (pq-rank rkid) (pq-rank lkid))

(vector (+ (pq-rank rkid) 1) item lkid rkid)

(vector (+ (pq-rank lkid) 1) item rkid lkid)))

(cond ((pq-empty? p1) p2)

((pq-empty? p2) p1)

((lt? (pq-item p2) (pq-item p1))

(pq-swap (pq-item p2) (pq-lkid p2)

(pq-merge lt? p1 (pq-rkid p2))))

(else (pq-swap (pq-item p1) (pq-lkid p1)

(pq-merge lt? (pq-rkid p1) p2)))))

(define (pq-insert lt? x pq)

(pq-merge lt? (vector 1 x pq-empty pq-empty) pq))

(define (pq-first pq)

(if (pq-empty? pq)

(error 'pq-first "empty priority queue")

(pq-item pq)))

(define (pq-rest lt? pq)

(if (pq-empty? pq)

(error 'pq-rest "empty priority queue")

(pq-merge lt? (pq-lkid pq) (pq-rkid pq))))

(define (lt? a b)

(or (< (car a) (car b))

(and (= (car a) (car b))

(< (cdr a) (cdr b)))))

(let ((first? 2) (second? 3) (prev 3)

(pq (pq-insert lt? (cons 9 6) pq-empty)))

(lambda ()

(if first? (begin (set! first? #f) 2)

(if second? (begin (set! second? #f) 3)

(let loop1 ((n (+ prev 2)))

(if (< n (car (pq-first pq)))

(let ((c (* n n)) (s (+ n n)))

(set! prev n)

(set! pq (pq-insert lt? (cons c s) pq))

n)

(let loop2 ()

(if (< n (car (pq-first pq)))

(loop1 (+ n 2))

(let* ((c (car (pq-first pq)))

(s (cdr (pq-first pq)))

(cs (cons (+ c s) s)))

(set! pq (pq-insert lt? cs (pq-rest lt? pq)))

(loop2)))))))))))

Here’s the timing test; the Sieve of Eratosthenes is a good algorithm, but the implementation using priority queues is very slow:

`> (time (sum-primes (gen-oneill) 1000000))`

(time (sum-primes (gen-oneill) ...))

3645 collections

91042 ms elapsed cpu time, including 2164 ms collecting

91184 ms elapsed real time, including 2245 ms collecting

30695660288 bytes allocated, including 30633126688 bytes reclaimed

7472966967499

Our fourth, and final, generator is based on a segmented variant of the Sieve of Eratosthenes. The code is moderately complex, and it requires space that grows as the square root of the size of the primes being generated to store the sieving primes plus a constant amount of space to store the sieve, but against these disadvantages it is very fast; if you can afford the space, this is the method of choice:

`(define (gen-sieve)`

(define (prime? n)

(if (even? n) (= n 2)

(let loop ((d 3))

(cond ((< n (* d d)) #t)

((zero? (modulo n d)) #f)

(else (loop (+ d 2)))))))

(define (init)

(let ((ps (list)) (qs (list))

(sv (make-vector 50000 #t)))

(do ((p 3 (+ p 2))) ((< 100000 (* p p)))

(when (prime? p) (set! ps (cons p ps))))

(set! qs (map (lambda (p) (+ (* 1/2 (- p 1)) p)) ps))

(do ((ps ps (cdr ps)) (qs qs (cdr qs)))

((null? ps))

(let ((p (car ps)) (q (car qs)))

(do ((i q (+ i p))) ((<= 50000 i))

(vector-set! sv i #f))))

(values ps qs sv)))

(define (advance ps qs sv bot)

(do ((i 0 (+ i 1))) ((= i 50000))

(vector-set! sv i #t))

(set! qs (map (lambda (p q) (modulo (- q 50000) p)) ps qs))

(do ((p (+ (car ps) 2) (+ p 2)))

((< (+ bot 100000) (* p p)))

(when (prime? p)

(set! ps (cons p ps))

(set! qs (cons (/ (- (* p p) bot 1) 2) qs))))

(do ((ps ps (cdr ps)) (qs qs (cdr qs)))

((null? ps))

(let ((p (car ps)) (q (car qs)))

(do ((i q (+ i p))) ((<= 50000 i))

(vector-set! sv i #f))))

(values ps qs sv))

(let-values (((ps qs sv) (init))

((bot next-i next-p) (values 0 1 2)))

(lambda ()

(let ((result next-p))

(let loop ((i next-i))

(cond ((= i 50000)

(set! bot (+ bot 100000))

(let-values (((p q s)

(advance ps qs sv bot)))

(set! ps p) (set! qs q)

(set! sv s) (set! next-i 0))

(loop 0))

((vector-ref sv i)

(set! next-i (+ i 1))

(set! next-p (+ bot i i 1))

result)

(else (loop (+ i 1)))))))))

We used the same primality test by trial division as the brute force generator, because for small primes, such as the sieving primes, itâ€™s faster than the alternatives. Variable *sv* is the bitarray of the sieve, which contains only odd numbers, and variable *bot* is the even number just below the smallest number in the current segment, which are hard-coded at intervals of 100000. Variable *ps* is the list of sieving primes, in descending order. Variable *qs* corresponds to *ps*, and holds the index in the sieve bitarray of the smallest multiple of the corresponding sieving prime in the current segment. `Init`

collects the sieving primes less than 100000 in the first `do`

, computes the corresponding *qs* in the `map`

, and sieves each of the sieving primes in the second `do`

, using the third (nested) `do`

to mark off multiples. `Advance`

resets for the next segment, clearing the bitarray in the first `do`

, calculating the new *qs* in the `map`

, extending the *ps* and *qs* lists for the new sieving primes in the second `do`

, and sieving in the third and fourth (nested) `do`

. The *loop* after the `lambda`

finds the next set bit in the sieve, resetting for the next segment when the current segment is exhausted. Variable *next-i* is the next sieve location to be checked for primality, and variable *next-p* is the next unreported prime, which is always calculated in advance of its need. Here’s the timing test:

`> (time (sum-primes (gen-sieve) 1000000))`

(time (sum-primes (gen-sieve) ...))

7 collections

1832 ms elapsed cpu time, including 4 ms collecting

1905 ms elapsed real time, including 6 ms collecting

32659704 bytes allocated, including 29472880 bytes reclaimed

7472966967499

Finally, we answer the original question; here’s the sum of the first billion primes:

`> (time (sum-primes (gen-sieve) 1000000000))`

(time (sum-primes (gen-sieve) ...))

23357 collections

2034715 ms elapsed cpu time, including 14597 ms collecting

2173303 ms elapsed real time, including 15477 ms collecting

98382285776 bytes allocated, including 98384545808 bytes reclaimed

11138479445180240497

That’s 33:54.7 minutes, or about half a million primes per second. Which is really rockin’ big-time. You can see more of these prime sums at http://oeis.org/A007504/a007504.txt.

You can run the program at http://programmingpraxis.codepad.org/hbNkJxt5, but only for the first ten thousand primes due to time constraints.

Pages: 1 2

The above C++ code sums primes using my primesieve library (https://primesieve.googlecode.com). To compile it on a Linux/Unix system use:

This takes about 10 seconds on my Intel Core-i5 CPU.

A (inefficient) Python solution:

On my machine (Intel Core i3) this takes around 87 seconds to complete.

Java noob’s super inefficient, but extensively documented, Java

Done in SwiftForth with a bitset library I wrote a long time ago. Took 40 minutes or 410K primes per second. (While also watching web video, etc. on the computer.) It uses the compressed 33K file from previous exercise to store primes < 1 million, which is used as the sieving primes, and the segmented sieve from another previous exercise to sieve blocks after 1 million, in increments of 100,000.

requires bitset

\ Table lookup for "small" primes, (33K table for primes < 1e6)

1,000,003 drop Constant FILE_PRIME_MAX

: load-primes ( str — addr )

r/o bin open-file throw locals| fd |

fd file-size throw drop ( — size )

s" CREATE prime-table" evaluate

here over allot

swap fd read-file throw drop

fd close-file throw ;

s" ../prime1e6.dat" load-primes

hex

create masks[]

FF c, \ 0

FE c, FE c, FE c, FE c, FE c, FE c, \ 1 – 6

FC c, FC c, FC c, FC c, \ 7 – 10

F8 c, F8 c, \ 11 – 12

F0 c, F0 c, F0 c, F0 c, \ 13 – 16

E0 c, E0 c, \ 17 – 18

C0 c, C0 c, C0 c, C0 c, \ 19 – 22

80 c, 80 c, 80 c, 80 c, 80 c, 80 c, \ 23 – 28

00 c, \ 29

decimal

create offset_mod_11

-1 , 1 , 7 , -1 , 11 , 17 , -1 , 29 , 13 , 23 , 19 ,

: lowbit>offset

dup negate and 11 mod cells offset_mod_11 + @ ;

: next-small-prime ( n — n )

dup 2 < IF drop 2 EXIT THEN

dup 3 < IF drop 3 EXIT THEN

dup 5 < IF drop 5 EXIT THEN

dup FILE_PRIME_MAX >= abort" : precomputed prime table exceeded"

30 /mod prime-table +

swap masks[] + c@ \ addr mask

over c@ and lowbit>offset

BEGIN dup 0< WHILE

drop

1+ dup c@ lowbit>offset

REPEAT

swap prime-table – 30 * + ;

\ segmented sieve

100,000 drop Constant SIEVE_BLOCK_SIZE

SIEVE_BLOCK_SIZE 2/ bset sieve

2variable sieve_start \ used by the generator

: sieve_end ( — d )

sieve_start 2@ [ SIEVE_BLOCK_SIZE 1- ] Literal M+ ;

: d/mod ( d n — d%n d/n )

locals| n |

\ FORTH does not have remainder function for double division

\ so we multiply the quotient by the divisor and subtract…

\

2dup 1 n M*/ 2dup 2>r \ get quotient & save a copy

n 1 M*/ d- drop \ compute remainder

2r> ; \ restore quotient

: dmod ( d m — n )

locals| m |

m d/mod 2drop \ note: FM/MOD is faster but overflows…

dup 0< IF m + THEN ;

: offset ( n — n ) \ first offset into bit array of prime #

sieve_start 2@ third 1+ M+ D2/ dnegate rot dmod ;

: seg-sieve ( d — )

sieve_start 2!

sieve bits erase

sieve bset-invert! \ set everything to TRUE

3

BEGIN

dup offset

BEGIN dup sieve nip ( length ) < WHILE

dup sieve -bit

over +

REPEAT drop

next-small-prime

sieve_end third dup M* D< UNTIL

drop ;

\ gen-primes — generate primes and call callback for each one.

\ callback returns 0 when no more primes desired

\ After ~1e12 primes generated will throw exception…

variable 'with_prime

variable complete?

: sieve_cb ( n — n )

complete? @ IF

drop

ELSE

sieve_start 2@ rot 2* 1+ M+ 'with_prime @execute not complete? !

THEN ;

: gen-primes ( xt — )

'with_prime ! false complete? !

2

BEGIN

dup s>d 'with_prime @execute not IF drop EXIT THEN

next-small-prime

dup 1000000 > UNTIL drop

1,000,000

BEGIN

2dup seg-sieve

sieve ['] sieve_cb bset-foreach

complete? @ IF 2drop EXIT THEN

SIEVE_BLOCK_SIZE M+

AGAIN ;

\ sum first N primes

variable #primes

2variable sum

: sum_cb ( d — ? )

sum 2@ D+ sum 2!

-1 #primes +!

#primes @ 0> ;

: sum_primes ( n — d )

0, sum 2! #primes !

['] sum_cb gen-primes

sum 2@ ;

counter 1,000,000,000 drop sum_primes du. timer 11138479445180240497 2401035 ok

Trying this again, hope it formats better…

Done in SwiftForth with a bitset library I wrote a long time ago. Took 40 minutes or 410K primes per second. (While also watching web video, etc. on the computer.) It uses the compressed 33K file from previous exercise to store primes < 1 million, which is used as the sieving primes, and the segmented sieve from another previous exercise to sieve blocks after 1 million, in increments of 100,000.

requires bitset

\ Table lookup for "small" primes, (33K table for primes < 1e6)

1,000,003 drop Constant FILE_PRIME_MAX

: load-primes ( str — addr )

r/o bin open-file throw locals| fd |

fd file-size throw drop ( — size )

s" CREATE prime-table" evaluate

here over allot

swap fd read-file throw drop

fd close-file throw ;

s" ../prime1e6.dat" load-primes

hex

create masks[]

FF c, \ 0

FE c, FE c, FE c, FE c, FE c, FE c, \ 1 – 6

FC c, FC c, FC c, FC c, \ 7 – 10

F8 c, F8 c, \ 11 – 12

F0 c, F0 c, F0 c, F0 c, \ 13 – 16

E0 c, E0 c, \ 17 – 18

C0 c, C0 c, C0 c, C0 c, \ 19 – 22

80 c, 80 c, 80 c, 80 c, 80 c, 80 c, \ 23 – 28

00 c, \ 29

decimal

create offset_mod_11

-1 , 1 , 7 , -1 , 11 , 17 , -1 , 29 , 13 , 23 , 19 ,

: lowbit>offset

dup negate and 11 mod cells offset_mod_11 + @ ;

: next-small-prime ( n — n )

dup 2 < IF drop 2 EXIT THEN

dup 3 < IF drop 3 EXIT THEN

dup 5 < IF drop 5 EXIT THEN

dup FILE_PRIME_MAX >= abort" : precomputed prime table exceeded"

30 /mod prime-table +

swap masks[] + c@ \ addr mask

over c@ and lowbit>offset

BEGIN dup 0< WHILE

drop

1+ dup c@ lowbit>offset

REPEAT

swap prime-table – 30 * + ;

\ segmented sieve

100,000 drop Constant SIEVE_BLOCK_SIZE

SIEVE_BLOCK_SIZE 2/ bset sieve

2variable sieve_start \ used by the generator

: sieve_end ( — d )

sieve_start 2@ [ SIEVE_BLOCK_SIZE 1- ] Literal M+ ;

: d/mod ( d n — d%n d/n )

locals| n |

\ FORTH does not have remainder function for double division

\ so we multiply the quotient by the divisor and subtract…

\

2dup 1 n M*/ 2dup 2>r \ get quotient & save a copy

n 1 M*/ d- drop \ compute remainder

2r> ; \ restore quotient

: dmod ( d m — n )

locals| m |

m d/mod 2drop \ note: FM/MOD is faster but overflows…

dup 0< IF m + THEN ;

: offset ( n — n ) \ first offset into bit array of prime #

sieve_start 2@ third 1+ M+ D2/ dnegate rot dmod ;

: seg-sieve ( d — )

sieve_start 2!

sieve bits erase

sieve bset-invert! \ set everything to TRUE

3

BEGIN

dup offset

BEGIN dup sieve nip ( length ) < WHILE

dup sieve -bit

over +

REPEAT drop

next-small-prime

sieve_end third dup M* D< UNTIL

drop ;

\ gen-primes — generate primes and call callback for each one.

\ callback returns 0 when no more primes desired

\ After ~1e12 primes generated will throw exception…

variable 'with_prime

variable complete?

: sieve_cb ( n — n )

complete? @ IF

drop

ELSE

sieve_start 2@ rot 2* 1+ M+ 'with_prime @execute not complete? !

THEN ;

: gen-primes ( xt — )

'with_prime ! false complete? !

2

BEGIN

dup s>d 'with_prime @execute not IF drop EXIT THEN

next-small-prime

dup 1000000 > UNTIL drop

1,000,000

BEGIN

2dup seg-sieve

sieve ['] sieve_cb bset-foreach

complete? @ IF 2drop EXIT THEN

SIEVE_BLOCK_SIZE M+

AGAIN ;

\ sum first N primes

variable #primes

2variable sum

: sum_cb ( d — ? )

sum 2@ D+ sum 2!

-1 #primes +!

#primes @ 0> ;

: sum_primes ( n — d )

0, sum 2! #primes !

['] sum_cb gen-primes

sum 2@ ;

counter 1,000,000,000 drop sum_primes du. timer 11138479445180240497 2401035 ok

[...] This problem from Programming Praxis came about in the comments to my last post and intrigued me. So today, we are trying to sum the first one billion primes. Summing the first hundred, thousand, even million primes isn’t actually that bad. But it takes a bit more effort when you scale it up to a billion. And why’s that? [...]

I know it’s an older, but after your comments on my solution to the Pythagorean Triples hinting at this one, I had to try it. I ended up working on it way more than I probably should have with quals coming up, but what I ended up with is 5 different ways (including all three sieves mentioned on Wikipedia) of summing the first n primes with different data structure variants on the two fastest ones.

It still ends up taking an hour and a half on the quickest run, but it was really interesting to work out all of the ways to do it. Perhaps I’ll see if I can optimize even more at some point. Although 10 seconds? Likely not. :)

Linky: The Sum of the First Billion Primes

Five methods in Perl.

The first is calling Math::Prime::Util::next_prime in a dumb loop. Not very fast since it’s doing trial division and/or MR tests. 400k-500k / second.

We can speed that up by having MPU precalculate all the primes, obviously at the expense of memory (about 760MB for sieving 22.8B numbers). Using nth_prime_upper() to get an upper bound (0.01% larger than the real value, but obtained in microseconds) we can do this pretty fast. A reasonably fast solution at over 3M primes/s.

Next is using Math::Prime::Util to do it more efficiently — get primes in segments until we’ve reached our limit. Not bad — 66s on my machine to sum the first 1 billion. Over 15M/s.

Now we move to pure Perl. First let’s use an unsegmented sieve. This one is a modification of one from c2.com’s wiki, which is a very simple SoE, and much faster than most Perl sieves found on the web (I have a collection of 17 of them — some shockingly bad, some quite decent). It runs at about 260k/s. But the biggest problem is that it isn’t segmented, nor is it storing the numbers efficiently. My 32GB machine started swapping when calculating 10^8.

Lastly is a segmented sieve in pure Perl using strings. A bit wacky and too verbose, but it can be faster than the obvious solutions depending on memory speed. As a basic unsegmented sieve, it’s about 2x faster than any of the other Perl solutions on my workstation. On my old Atom netbook it’s a bit slower than the above sieve. I wrote it earlier this year so Math::Prime::Util could have something reasonable as a fallback if the XS failed to compile on a platform. Since it’s segmented it will work for our task without going crazy with memory. Over 500k/s.

None of them compare to primesieve of course (the serial version of Kim’s program takes all of 7 seconds on my machine, the parallel version runs in 1.1s). The callback is spiffy also. I thought about adding something like it to Math::Prime::Util (e.g. prime_foreach 2 100 { …sub… }) and still might, but calling Perl subroutines is far slower than C — it’s over a minute just to make 1B empty subroutine calls so it seems of limited use for this example.

Timings:

Code:

Dang. After some comments over on my original post, I decided to go back and add a the segmented version of the Sieve of Eratosthenes into the mix. I’m glad I did.

While my previous times were 2 hr 42 min for Eratosthenes and 1 hr 28 min for Atkin, the new segmented sieve blows both out of the water at only 25 min 12 sec. It’s still nowhere near as quick as some people’s, but it’s at least a good example of what being conscious of what memory/caching behavior can do to runtimes.

Linky: One Billion Primes – Segmented Sieve

Alright, here’s my approach (quite literally).

On my Intel Core i7 2.3 ghz machine, it completes in 495 milliseconds and uses about 800,000 bytes of RAM (but if I used a larger wheel that would go up rapidly).

One interesting side note: the actual algorithm I’m using doesn’t use any memory during run time aside from the pre-allocated memory of the wheels and the stack space of the function calls (which will never be deeper than log n/log 2), so it would be relatively trivially to make this algorithm multi-threaded or even distributed. My 495 ms time is single-threaded. With that said, this algorithm runs in something worse than O(n^4/5) time, so there are faster solutions.

My C# implementation follows. Just call Program.Main(). This code handles overflow very poorly – if you try values of n larger than 22801763489, or increasing the wheel size, there’s a good chance you’ll start seeing garbage values.