primes

Some prime number algorithms, mostly sieves. Benchmarks:

$ python benchmark.py
N triv simp era0 era1 era2 era3 era4 era5 era6 era7 era8 era9
------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- ------- -------
1.0M >1s 96.45 2.87 2.85 2.44 1.65 1.83 1.62 1.57 1.46 1.56 0.91
1.3M >1s 133.82 3.40 3.40 2.13 1.83 2.24 1.83 1.95 1.97 1.40 1.06
1.6M >1s 186.44 4.12 4.05 2.96 1.91 2.70 2.00 2.10 1.73 1.32 1.40
2.0M >1s 261.25 5.92 5.63 3.00 2.28 2.98 2.25 2.64 1.87 1.46 1.73
2.6M >1s 360.36 6.96 6.03 4.07 2.49 3.59 2.42 2.61 2.17 1.84 1.06
3.3M >1s 505.69 9.23 7.19 4.19 3.02 4.31 2.97 2.95 2.63 1.76 1.93
4.2M >1s 708.60 12.81 9.80 4.82 3.57 5.02 3.48 3.69 3.37 1.93 1.52
5.3M >1s >1s 14.79 10.99 5.89 4.53 6.18 4.32 4.18 3.78 2.35 1.79
6.7M >1s >1s 19.56 13.99 7.34 4.99 7.65 4.71 5.10 4.30 2.96 1.45
8.5M >1s >1s 25.04 17.63 9.13 6.21 9.30 6.18 6.25 5.28 3.12 1.59
10.8M >1s >1s 32.48 23.95 11.71 7.71 11.36 7.38 7.66 6.59 4.07 2.06
13.7M >1s >1s 42.44 32.40 14.47 8.82 13.80 8.99 9.33 7.51 4.26 2.60
17.4M >1s >1s 61.88 42.95 19.19 11.44 17.61 10.89 11.40 9.38 5.21 2.40
22.1M >1s >1s 90.01 56.35 24.34 14.56 21.55 14.04 14.26 11.95 6.34 2.97
28.1M >1s >1s 127.14 74.00 33.27 18.28 27.41 17.70 18.14 14.97 7.89 3.25
35.6M >1s >1s 177.53 95.26 44.61 23.89 33.81 21.75 22.79 19.07 9.68 3.66
45.2M >1s >1s 240.48 124.83 58.86 33.11 45.94 27.94 28.37 23.28 12.39 4.82
57.4M >1s >1s 318.85 159.92 77.10 44.09 55.48 36.74 37.39 30.27 16.40 6.00
72.8M >1s >1s 425.98 209.65 101.14 60.37 72.07 47.26 44.55 37.11 19.81 6.90
92.4M >1s >1s 563.49 279.82 132.98 81.96 86.63 58.88 60.64 50.24 25.99 8.67
117.2M >1s >1s 744.33 358.16 170.27 99.92 112.75 76.88 71.99 60.64 34.65 11.58
148.7M >1s >1s >1s 495.27 220.13 131.91 142.11 88.22 92.12 73.98 46.31 14.17
188.7M >1s >1s >1s 675.12 297.59 172.19 208.07 112.99 126.48 108.19 56.52 19.46
239.5M >1s >1s >1s 903.49 391.23 221.35 245.96 144.35 174.01 121.32 72.31 23.56
303.9M >1s >1s >1s >1s 541.06 302.64 303.65 191.49 198.22 153.02 95.13 32.62
385.7M >1s >1s >1s >1s 726.35 427.34 391.30 238.71 248.83 198.50 122.30 43.70
489.4M >1s >1s >1s >1s >1s 546.64 502.92 314.65 337.60 252.66 154.78 54.44
621.0M >1s >1s >1s >1s >1s 793.78 706.32 456.51 408.93 334.38 203.16 66.73
788.0M >1s >1s >1s >1s >1s >1s 899.35 518.50 532.83 428.91 262.75 93.48
1000.0M >1s >1s >1s >1s >1s >1s >1s 696.30 685.83 552.79 331.99 122.19

bench

For comparison, something actually optimised (not for counting, like the sieves here):

$ primesieve -t1 1e9
Sieve size = 256 KiB
Threads = 1
100%
Seconds: 0.100
Primes: 50847534

There seems to also be some overhead on just a simple invocation of primesieve; hyperfine consistently reports lower numbers:

$ hyperfine 'primesieve -t1 1e9' 'taskset -c 0-3 ./p -e9 1000000000'
Benchmark 1: primesieve -t1 1e9
 Time (mean ± σ): 86.0 ms ± 4.8 ms [User: 84.9 ms, System: 0.9 ms]
 Range (min ... max): 79.3 ms ... 96.5 ms 30 runs
Benchmark 2: taskset -c 0-3 ./p -e9 1000000000
 Time (mean ± σ): 130.4 ms ± 7.4 ms [User: 128.1 ms, System: 1.0 ms]
 Range (min ... max): 118.9 ms ... 145.8 ms 22 runs
Summary
 primesieve -t1 1e9 ran
 1.52 ± 0.12 times faster than taskset -c 0-3 ./p -e9 1000000000```

$ lscpu -C
NAME ONE-SIZE ALL-SIZE WAYS TYPE LEVEL SETS PHY-LINE COHERENCY-SIZE
L1d 48K 352K 12 Data 1 64 1 64
L1i 32K 576K 8 Instruction 1 64 1 64
L2 1.3M 6.5M 10 Unified 2 2048 1 64
L3 12M 12M 12 Unified 3 16384 1 64