A new prime sieve

baric

Can't write code?!?

aww, man.. that's the easy part! :)

epsi00

well, if that's the easy part, you are welcome to experiment numerically with this sieve and take full credit for it. I am really curious to see how far we can go before we hit the rule of diminishing return. Obviously we can't keep improving the efficiency at little or no cost.

baric

Like I said, it's totally dependent upon the computer's memory capacity although the size of the sieve does go up factorially with {p-1.. } where p is the series of primes, so you can't really get too far...

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.

epsi00

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.

bsquared

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).

Ulam

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

idiom

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