Re: Sieve superior to Eratosthenes
> Please forgive my curtness, but have you read all the material by, for example, Sorenson?--no. However, prodded by you, I just looked at
> --Phil Carmody
"The pseudosquares prime sieve" by Jonathan P. Sorensen 2006 and some other stuff
The particular algorithm advanced by JPS in this paper looks like a clearly bad idea.
His review of other work, contains these claims:
JPS CLAIM 1. the fastest known sieves take O(N/loglogN) time.
This is even faster than mine, which in turn is faster than Eratosthenes.
To back this up he cites: P.Pritchard CACM 24,1 (1981) 18-23 & 772
and B.Dunten, J.Jones, JP Sorensen: Info Proc Lett 59 (1996) 79-84.
I have not seen Pritchard but did see D+J+S 1996 and the latter is completely useless
because it requires huge memory.
JPS CLAIM 2. Memory in some (other) sieves can be reduced to O(N^(1/3)) or even O(N^(1/4)), perhaps with aid of conjectures. I'm doing better than that, I can reduce to O(N^(1/K)) for any fixed integer K.
The idea behind my sieve is extremely simple. Simply sieve enough to get a set of primes
and nonprimes that is small (no more than a constant times the primes alone) and then test these using the $640 primality test. (I also use a "wheel" idea in 2 ways to save loglogN time factors during the sieving to prevent the time use from being superlinear.)
"Pritchard's Wheel Sieve" as described here
and this description is pretty much exactly the same as "step 2" in my algorithm, and takes order N time.
This contradicts Sorensen's claim that Pritchard achieves O(N/loglogN) time.
So there must have been another idea too. I can see one way to accomplish sublinear time
(perhaps the idea Pritchard had?) which is (basically) that you only sieve out multiples M*P of primes P where M is still possibly-prime according to your current partially-sieved table. This would be a pyrrhic victory since you'd need immense memory consumption to do it.
Is any method known that achieves sublinear time and way-sublinear memory simultaneously? I know of none.
The best I know is way-sublinear memory and linear time (my method) but I only achieve that by using the $640 primality test which probably ultimately will fail, hence my algorithm actually is presumably wrong. This in practice seems irrelevant since the first failure is way larger than anybody will ever sieve.
[Incidentally in my algorithm step 2, one could omit the wheel and just use Eratosthenes, thus suffering a loglogN factor time-use expansion in theory, but in practice it might be faster for a long way. There's a lot of games like that one could play to speed up