Register to reply 
A new prime sieveby epsi00
Tags: primes sieve 
Share this thread: 
#19
May211, 12:37 PM

P: 84




#20
May211, 01:08 PM

P: 12

If you set the sieve limit to 1 billion, for example, your prime sieve stops at p(10)=29... i.e E!{p(1)1*p(2)1... *p(10)1} = 1,021,870,080. At that point, you are filtering 84.2% of the integers. Adding 31 to the sieve increases the sieve size to 30 billion and raises the filtering to 84.7%, or an improvement of 3.33% (31/30). In addition, each entry in the sieve would occupy multiple bytes since we would be dealing with very large integers. (8 bytes each would allow representation of integers up to 1.8E19). So a sieve of 30 billion in size would require 240 gigabytes to maintain. The realistic memory limit has to be around there because I doubt that anyone would want to designate several terabytes of memory to maintain a sieve of {2...37} I guess you could write the program to query the heap space and automatically limit the sieve size to the computer's memory capacity. It would not be a bad way to do it since a 3% improvement over the factorization of 1.8E19 numbers is going to save a lot more time than it takes to set up the sieve. Then you could simply throw more hardware (memory) at the problem to speed things up. I'll see if I can write up some code for this tonight. 


#21
May211, 02:41 PM

P: 84

Sometimes one may be interested in sieving between two numbers (N1,N2) instead of from (1,N). This sieve can probably be adapted to do that ( I haven't thought seriously about this case ). It's just a matter of figuring out how to calculate the max element of each column for the sieve of (1,N) then start from those max element and calculate the elements of columns up to N.



#22
Nov711, 08:51 AM

P: 1

This is an interesting variation of the wheel sieve, but I don't have any idea how efficiently it could be implemented versus a classic wheel. Especially if extended to larger residue class systems (i.e., mod 30 or mod 210).
My own sieve currently uses wheel sieves up to mod 2310 (2*3*5*7*11) for sieving large ranges of the number line, and is one of the fastest sieve of eratosthenes implementations I'm aware of. I've spent enough time optimizing it that I don't have any interest in coding this variation, but I encourage you to learn how to do it yourself. I'll note that returns diminish sufficiently that mod 2310 is as high as I could go before the sieve speed actually started to decrease (mod 30030 involves sieving over too many residue classes). 


#23
Nov711, 10:36 AM

P: 5

If you want be happy, you can arrest the algorithm at [tex]\sqrt{n}[/tex].



#24
Nov1711, 07:46 PM

P: 20

Hey this is correct but you can actually reduce to 1/5



Register to reply 
Related Discussions  
Twin Prime Sieve  Linear & Abstract Algebra  2  
Goldbach’s Conjecture and the 2Way Sieve  General Math  6  
An algorithm based on Eratosthenes Sieve  Programming & Computer Science  6  
Sieve of Eratosthenes  Programming in VB  Computing & Technology  14 