primesum is a command-line program that computes the sum of the primes below an integer x ≤ 1031 as quickly as possible using a modified version of the combinatorial prime counting function algorithm [1]. primesum has already been used to compute many new prime sum world records!
primesum is a modified version of the author's primecount program.
Below are the latest precompiled binaries for Windows, Linux and macOS. These binaries are statically linked and require a CPU which supports the POPCNT instruction (2010 or later).
- primesum-1.7-win64.zip, 525 KB
- primesum-1.7-linux-x64.tar.xz, 837 KB
- primesum-1.7-macOS-x64.zip, 353 KB
You need to have installed a C++ compiler, cmake and make. Ideally primesum should be compiled using a C++ compiler that supports both OpenMP and 128-bit integers (e.g. GCC, Clang, Intel C++ Compiler).
cmake .
make -j
sudo make installOpen a terminal and run primesum using e.g.:
# Sum the primes below 10^14
./primesum 1e14
# Print progress and status information during computation
./primesum 1e18 --status
# Use 4 threads
./primesum 1e14 --threads=4 --timeUsage: primesum x [OPTION]...
Sum the primes below x <= 10^31 using fast implementations of the
combinatorial prime summing function.
Options:
-d, --deleglise_rivat Sum primes using Deleglise-Rivat algorithm
-l, --lmo Sum primes using Lagarias-Miller-Odlyzko
-s[N], --status[=N] Show computation progress 1%, 2%, 3%, ...
[N] digits after decimal point e.g. N=1, 99.9%
--test Run various correctness tests and exit
--time Print the time elapsed in seconds
-t<N>, --threads=<N> Set the number of threads, 1 <= N <= CPU cores
-v, --version Print version and license information
-h, --help Print this help menu
Advanced Deleglise-Rivat options:
-a<N>, --alpha=<N> Tuning factor, 1 <= alpha <= x^(1/6)
--P2 Only compute the 2nd partial sieve function
--S1 Only compute the ordinary leaves
--S2_trivial Only compute the trivial special leaves
--S2_easy Only compute the easy special leaves
--S2_hard Only compute the hard special leaves
primesum scales nicely up until 10^23 on current CPUs. For larger values primesum's large memory usage causes many TLB (translation lookaside buffer) cache misses that severely deteriorate primesum's performance. Fortunately the Linux kernel allows to enable transparent huge pages so that large memory allocations will automatically be done using huge pages instead of ordinary pages which dramatically reduces the number of TLB cache misses.
sudo su
# Enable transparent huge pages until next reboot
echo always > /sys/kernel/mm/transparent_hugepage/enabled
echo always > /sys/kernel/mm/transparent_hugepage/defrag| x | Sum of the primes below x | Time elapsed |
| 1010 | 2,220,822,432,581,729,238 | 0.01s |
| 1011 | 201,467,077,743,744,681,014 | 0.02s |
| 1012 | 18,435,588,552,550,705,911,377 | 0.04s |
| 1013 | 1,699,246,443,377,779,418,889,494 | 0.11s |
| 1014 | 157,589,260,710,736,940,541,561,021 | 0.36s |
| 1015 | 14,692,398,516,908,006,398,225,702,366 | 1.16s |
| 1016 | 1,376,110,854,313,351,899,159,632,866,552 | 3.66s |
| 1017 | 129,408,626,276,669,278,966,252,031,311,350 | 14.60s |
| 1018 | 12,212,914,292,949,226,570,880,576,733,896,687 | 66.66s |
| 1019 | 1,156,251,260,549,368,082,781,614,413,945,980,126 | 330.01s |
| 1020 | 109,778,913,483,063,648,128,485,839,045,703,833,541 | 1486.87s |
The benchmarks above were run on an Intel Core i7-6700 CPU (4 x 3.4 GHz) from 2015 using a Linux x64 operating system and primesum was compiled using GCC 6.4.
A046731 world records
| x | Sum of the primes below x | Date | Computed by |
| 1021 | 10449550362130704786220283253063405651965 | June 6, 2016 | Kim Walisch |
| 1022 | 996973504763259668279213971353794878368213 | June 6, 2016 | Kim Walisch |
| 1023 | 95320530117168404458544684912403185555509650 | June 11, 2016 | Kim Walisch |
| 1024 | 9131187511156941634384410084928380134453142199 | June 17, 2016 | David Baugh |
| 1025 | 876268031750623105684911815303505535704119354853 | Oct. 16, 2016 | David Baugh |
| 1026 | 84227651431208862537105979544170116745778105437780 | May. 25, 2022 | Kim Walisch |
Note that the sum of the primes below 10^21 was already correctly computed by Marc Deléglise in 2009 but when he verified the result using his program he found a different result (off by 1) so he withdrew his result in 2011.
A099824 world records
| n | Sum of the first n primes | Date | Computed by |
| 1018 | 21849887810843912935127758942358047227 | June 5, 2016 | Kim Walisch |
| 1019 | 2302808849326957165657230565155878163277 | June 5, 2016 | Kim Walisch |
| 1020 | 242048824942159504049568772767666927073373 | June 5, 2016 | Kim Walisch |
| 1021 | 25380411223557757489768734384174904646137001 | June 11, 2016 | Kim Walisch |
| 1022 | 2655479563137417712148525630666125075397977159 | June 22, 2016 | David Baugh |
| 1023 | 277281399946560013844427926899019949823102890613 | Sep. 26, 2016 | David Baugh |
| 1024 | 28900534863094599803598612528087047372125211931087 | June 17, 2022 | Kim Walisch |
A130739 world records
| n | Sum of the primes < 2^n | Date | Computed by |
| 271 | 57230460176857192458791870659870195302414 | Dec. 26, 2017 | Kim Walisch |
| 272 | 225709510085333603256262210540764048485810 | Dec. 26, 2017 | Kim Walisch |
| 273 | 890344379866902468590503993853978913148982 | Dec. 26, 2017 | Kim Walisch |
| 274 | 3512767258692956754932236839569828523905141 | Dec. 26, 2017 | Kim Walisch |
| 275 | 13861865005427848960138734445963535022604898 | Dec. 26, 2017 | Kim Walisch |
| 276 | 54710756810055087402063527107893581408200826 | Dec. 26, 2017 | Kim Walisch |
| 277 | 215973500680654121229780243886194476543303643 | Dec. 26, 2017 | Kim Walisch |
| 278 | 852713035956963663153441533770552801919275705 | Dec. 26, 2017 | Kim Walisch |
| 279 | 3367271267053300856599603567833163229921782198 | Dec. 26, 2017 | Kim Walisch |
| 280 | 13299160452380363326976224185417674340116996121 | Dec. 26, 2017 | Kim Walisch |
- M. Deléglise and Jean-Louis Nicolas, Maximal product of primes whose sum is bounded, 3 Jul 2012, https://arxiv.org/abs/1207.0603.