20220910, 07:56  #45 
Jul 2022
2^{2}·13 Posts 
I don't want to waste anyone's time but I don't have a highperformance PC available. The only comparison I was able to make is on ideone.com and kimwalisch/segmented_bit_sieve gives the result in 1.24s for n=10^9 instead this wheel_sieve gives the result in 0.96s for n=10^9 and modulus 210.
I would like to understand if the sieve is performing, does anyone have a chance to make a comparison for n=10^12 and modulus 2310, input segmented_bit_sieve_wheel(1000000000000,2310). 
20220928, 07:04  #46 
Jul 2022
2^{2}·13 Posts 

20220928, 08:20  #47 
Romulan Interpreter
"name field"
Jun 2011
Thailand
2805_{16} Posts 
There are many tools to sieve for primes. Former versions of yafu can also do it (I believe that in the newer versions Ben moved this out like a standalone program?). Can you beat yafu?
Last fiddled with by LaurV on 20220928 at 08:35 
20220928, 13:10  #48  
"Ben"
Feb 2007
E89_{16} Posts 
Quote:
But anyway, I tried it. I compiled with icpc O2 g time ./wheel_test primes count= 5761455 0.095u 0.001s 0:00.29 31.0% 0+0k 0+0io 0pf+0w compared to ./yafu "primes(0,100000000)" elapsed time = 0.0114 ans = 5761455 And then with 10^9 / 30 for the second parameter I get time ./wheel_test primes count= 50847534 2.174u 0.001s 0:02.79 77.7% 0+0k 440+0io 1pf+0w compared to ./yafu "primes(0,1000000000)" elapsed time = 0.1084 ans = 50847534 Ok, so maybe you want larger wheels... lets try 210. changing the n_PB variable to 4 and changing the second function parameter to 10^10 / 210 I get: time ./wheel_test primes count= 455052495 20.177u 0.003s 0:20.74 97.2% 0+0k 440+0io 1pf+0w compared to: ./yafu "primes(0,10000000000)" elapsed time = 1.1660 ans = 455052511 So. For me to test any further you need to explain better how to use your program to achieve correct results. Edit: Nevermind, I didn't see your original link to github, which works like you said and also gives correct results. I was using the stackexchange code you linked to later. Here are a couple timings for the 2310 wheel. 10^12 will take a while... time ./wheel_test primes < 10000000000: 455052511 10.787u 0.010s 0:11.24 95.9% 0+0k 408+0io 1pf+0w time ./wheel_test primes < 100000000000: 4118054813 204.513u 0.012s 3:25.03 99.7% 0+0k 408+0io 1pf+0w Last fiddled with by bsquared on 20220928 at 13:22 Reason: Trying newer code 

20220928, 13:31  #49 
Jul 2022
34_{16} Posts 
In sieve is a modified version of the Eratosthenes sieve with wheel factorization. In practice, the multiples of the primes of the base are not stored. This allows the use of less memory and even if more complex in theory it makes it faster.
In the link of the post #45 there is the version where the arrays C1 and C2 are calculated first this allows to use lower modulus values. Prime numbers from 0 to n are counted and the input is (n, modulus). In the first link of post #46 instead there is a version that can be used with larger numbers the input is k_start and k_end where is it k_start=n_start/bW and k_end=n_end/bW+1, but the coefficients are calculated from time to time is a little slower. 
20220928, 14:41  #50  
"Ben"
Feb 2007
61^{2} Posts 
Quote:
{1, 31, 61, 91, 121, ...} {7, 37, 67, 97, 127, ...} ... {29, 59, 89, 119, 149, ...} Each thread sieves its own array, and counts set bits in its array when finished. When the interval and wheel size is large, this is very efficient. When they are small it's not as efficient but, we don't care much because when they are small the sieve basically finishes instantly anyway. New result for 10^12, 2310: time ./wheel_test primes < 1000000000000: 37607912018 4342.279u 0.020s 1:12:23.04 99.9% 0+0k 408+0io 1pf+0w And for comparison: ./yafu "primes(0,10^11)" threads 1 elapsed time = 15.3575 ans = 4118054813 ./yafu "primes(0,10^12)" threads 1 elapsed time = 210.2783 ans = 37607912018 ./yafu "primes(0,10^11)" threads 8 elapsed time = 2.0205 ans = 4118054813 ./yafu "primes(0,10^12)" threads 8 elapsed time = 28.9238 ans = 37607912018 

20220928, 15:08  #51 
Jul 2022
2^{2}×13 Posts 

20220928, 15:25  #52 
"Ben"
Feb 2007
3721_{10} Posts 
You should not be discouraged, your sieve does very well and demonstrates knowledge of several important optimizations. And the 2310 version is definitely the best way to go for a huge interval like 10^12. Kim Walish and I have each put years and thousands of lines of code into our sieves, I show the comparisons just to illustrate what is possible.

20220929, 05:32  #53 
Romulan Interpreter
"name field"
Jun 2011
Thailand
3·5·683 Posts 
This was kind of expected, wasn't it? I mean, from the explanation for the Sundaram sieve they give on Wikipedia, you kinda sieve with all composites, while the classical way only sieves with primes. You expect a n/log increasing time. One interesting optimization would be to "tickle" that i+j+2ij in such a way to avoid repeating the sieving process multiple times for the same seed, as much as possible. I assume this is not easy or feasible...

20220930, 18:46  #54 
May 2004
FRANCE
1142_{8} Posts 
Sieving of (k*b^n+c)/d
Does somebody knows an efficient program to primesieve integers of the form (k*b^n+c)/d ? (d > 1 indeed!)
Thank you by advance! Jean Penné 
20221022, 07:13  #55 
Jun 2003
37×43 Posts 
You can use mtsieve to sieve k*b^n+c and sieve 2 to d1 and then from d+1 to max.

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 