20180124, 20:43  #1 
Mar 2016
2^{5}×13 Posts 
Sieve of Eratosthenes
A peaceful evening for all,
There is an implementation of the sieve of Eratosthenes with use of a heapconstruction and a bitwise used helparray availible: http://devalco.de/sieve_of_era.cpp Some few people will understand the construction and perhaps they like it. I got a runtime appr. 80 min for all prime <10^12 and an amazing small use of the memory. By the way, the code is a bit older, but the idea is still nice. Greetings from Eratosthenes Bernhard 
20180124, 21:06  #2  
"Ben"
Feb 2007
111010001011_{2} Posts 
Quote:
The "delete" and "include" stuff in the code had me thinking that the heap size was dynamic; i.e. that you were changing the size of the allocation in the loop (which would be bad). But after a bit more poking around that isn't the case, the size is fixed and elements are swapped around. All in all, a nice and compact implementation. I've added it to my collection of sieve of eratosthenes implementations that I've collected over the years Performance wise, there is still some room for improvement: Code:
primesieve 0 10^12 t48 Sieve size = 32 kilobytes Threads = 48 100% Primes : 37607912018 Seconds : 14.457 Code:
./yafu "primes(0,10^12)" threads 48 found 83224 sieving primes elapsed time = 12.1653 37607912018 

20180125, 01:45  #3 
Aug 2006
5,987 Posts 

20180125, 02:22  #4 
"Ben"
Feb 2007
3·17·73 Posts 
Yeah, and it is even better then that at lower upper bounds... 10^12 sized intervals are an ambitious undertaking.

20180125, 03:23  #5 
Aug 2006
13543_{8} Posts 

20180125, 04:10  #6  
Jun 2003
3^{4}·67 Posts 
Quote:
EDIT: Obviously no idea which CPU he used  quite possibly a much older CPU than what b^2 did. Last fiddled with by axn on 20180125 at 04:11 

20180125, 06:07  #7 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
3^{2}·101 Posts 
It's a neat and very small implementation. I also have a collection of sieves and benchmarks.
Note bsquared's results for yafu and primesieve are 48 threads. A big plus for yafu and primesieve, but I keep everything single threaded for easier comparison. I've added to my toolong todo list a note to make a web page with results and links to the codes / sources, as well as exact instructions on how to duplicate results (for those that are part of bigger projects). (Or maybe a github project?) Some of these are very small demo code, others quite large. Code:
Segmented sieves  10^9 10^10 10^11 10^12 10^13 yafu 0.285 1.876 20.241 4m 27.8s 54m 51s primesieve 5.4.2 0.119 1.661 23.480 4m 56.0s 58m 18s MPU 0.66b 0.132 2.022 33.620 6m 46.1s 91m 46s primegen 0.97 0.258 2.750 33.843 9m 43.1s 207m 56s MPU 0.66a 0.289 3.177 38.434 8m 30.6s 104m 48s MPU 0.41 0.320 3.529 42.971 9m 28.8s 119m 3s MPU 0.36 0.318 3.531 42.825 10m 25.3s TOeS v2 0.422 4.739 55.283 10m 41.7s 121m 3s Roy algo3 v2 0.435 5.087 64.456 12m 28.0s 150m 10s Flammenkamp 0.528 5.937 79.211 16m 24.1s tverniquet 0.643 6.937 80.876 17m 27.7s Roy algo3 v1 0.611 6.949 77.846 Walisch bit segmnt0.909 8.226 91.691 19m 9.9s TOeS v1 0.778 8.614 104.218 Walisch byte sgmnt0.890 13.213 208.519 Monolithic sieves: 10^9 10^10 10^11 10^12 Pari 2.6.2dev 0.998 9.940 1m 36.0s >3 hours MPU 0.36 0.907 12.333 2m 27.1s MPU 0.66 1.005 13.845 2m 55.7s // slower mach Mathisen 1998 1.820 21.197 3m 54.2s BHelmes Heap 1.989 21.813 4m 14.7s // < Zakiya 1.737 26.310 6m 34.9s Trivial odd SoE 2.529 30.018 6m 56.0s Lieberman 3.415 35.842 7m 2.5s Last fiddled with by danaj on 20180125 at 06:12 
20180125, 07:01  #8 
Aug 2006
5,987 Posts 

20180125, 07:03  #9  
Aug 2006
1763_{16} Posts 
Quote:
Do you, by chance, know of any good factoring sieves? PARI has one now but I'm disappointed with its performance. 

20180125, 07:31  #10 
Jun 2003
3^{4}×67 Posts 

20180125, 14:19  #11 
Aug 2006
5,987 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
New GPU accelerated sieve of Eratosthenes  cseizert  Programming  8  20161027 05:55 
Advantage of lattice sieve over line sieve  binu  Factoring  3  20130413 16:32 
Thinking of a new project: Sieve of Eratosthenes  XYYXF  Computer Science & Computational Number Theory  91  20130119 12:19 
Sieve of Eratosthenes  Raman  Programming  4  20090119 17:12 
Sieve of Eratosthenes  jchein1  Homework Help  6  20070827 13:51 