Talk:Sieve of Eratosthenes

From Wikipedia, the free encyclopedia

Apparently:

KOΣKINON EPATOΣΘENOϒΣ. or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers, by the Rev. Samuel Horsley, F. R. S. Samuel Horsley Philosophical Transactions (1683-1775), Vol. 62. (1772), pp. 327-347.

Is the paper that popularized this algorithm, if anyone wants to fill in historical details.

--Imran 21:15 13 Jun 2003 (UTC)

If a person wants fully working code, they can check code repositories. If a person wants performance hacks, they can check programmer's journals. Wikipedia is neither a code repository nor a programmer's journal.

Pseudocode is used on Wikipedia as a last resort to explain an algorithm, because most programming languages are not readable by common encyclopedia readers. There is also no excuse for repeating the fairly understandable explanation of the algorithm with pseudocode. Feel free, however, to insert external links to either. For an example, see Sieve of Atkin, which, while it does not have a good explanation yet, does have an external link to working, optimized code. — 131.230.74.194 21:28, 11 July 2005 (UTC)

[edit] "A Reduced Redundant Exclusions (RRE) Prime Sieve"

The main reason for the inefficiency of the Sieve of Eratosthenes is simply that it spends much time excluding non-primes which have already been excluded. This is not so apparent in the range 1- 100 where it is usually demonstrated. But a quick check of prime densities: 25 upto 100; 168 upto 1,000; 78,498 upto 1,000,000 and 50,847,534 upto 1,000,000,000 makes it obvious that a prime sieve that reduces the number of these redundant exclusions will go much faster. I was unable to check the Atkins Sieve due to it's complexity but a simple variation of the Sieve of Eratosthenes will vastly reduce redundant exclusions if not eliminate them altogether:

Step 1 Sequentially write down the integers from 2 to m

Step2 Cross out all numbers > 2; which are products of 2 and numbers in the table >=2

Step 3 Find the smallest remaining number >2; it is 3

Step 4 Cross out all numbers > 3; which are products of 3 and un-crossed out numbers, in the table, >=3

Step 5 Find the smallest remaining number >3; it is 5

Step 6 Cross out all numbers > 5; which are products of 5 and un-crossed out numbers, in the table, >=5

Step 7 Continue while " the smallest remaining number" squared is =< m

—The preceding unsigned comment was added by Rhnmcl (talk • contribs).

I'm sorry, but I don't see any difference with the algorithm in the article, except for redundancy in your description (all numbers >n are >=n). Qwertyus 12:46, 17 June 2006 (UTC)

Consider step 4 (for example); " the algorythm in the article " will cross out { 6,9,12,15,18, etc ); where 6,12,18 are redundant exclusions....they have already been crossed out ! Whereas step 4 (if read as I intend) will cross out only ( 9, 15, 21, 27, 33 etc} —The preceding unsigned comment was added by Rhnmcl (talk • contribs).

The article already states: The crossing-off of multiples can be started at the square of the number, as lower multiples have already been crossed out in previous steps. This saves a lot of time, particularly for large numbers. Qwertyus 15:30, 19 June 2006 (UTC)

A good first step is to disregard all multiples of two: that is, the sieve represents only odd numbers. This is easy enough, because the pattern is just as simple as for consecutive numbers, you just have to be careful ablout the starting point for striking out every third, fifth, seventh, etc. Having the sieve elements not represent multiples of three as well as more difficult, and matters worsen if even more primes are not represented. Possibly this is what the fancier method involves for a certain collection of primes to be skipped. Another ploy is to choose the seive length to be the product of the first few primes, say N, with the intention of producing a batch of primes over 0 to N - 1, then start again with N to 2N - 1 for a second batch, and so on for however many batches you wish (since in actual computers, sieve arrays cannot be of indefinite length). The point of this is that the initial pattern of the sieve is the same and so does not have to be prepared more than once. But one can do better...

[edit] No redundant exclusions

Nevertheless, it is irksome to sieve away and strike out elements that have previously been struck out when seiving with a smaller prime. This can be handled. So far, prime production is via division (test factorisation), and addition (seiving). Now comes prime production via multiplication, relying on the fundamental theorem of arithmetic that every number has a unique prime factorisation. The plan therefore is to generate all products of primes, and strike out the corresponding element of the seive: there will be one strike only on each composite number. Imagine a sieve of some large size. Start a process say "Breed" with two; it generates all powers of two and naturally, strikes them from the sieve up to the limit of the sieve. Further, for each power of two (being 1 to whatever) it takes that number and commands a Breed with that and three (the next higher prime) and five, and seven, and so forth until the multiple exceeds the seive length. Likewise start a basic Breed with three to generate all powers of three and further with those powers and the next primes up, five, seven, etc. And likewise a basic Breed with five, and so on, until the first level would start beyond the length of the seive. In this scheme it is helpful to schedule matters so that the smaller composite numbers are generated first so that the needed additional primes for the process can be extracted from the seive as it is being adjusted.

As for running speeds, the administration is much more complex. Clearly the multiplicative process requires time slightly less than linear with respect to the highest number N, being one action for every composite number, of which there are N less the number of primes up to N, or N - (N/Ln(N)) approximately, whereas the additive sieving method requires one pass for every prime less than the square root of N (very slightly less), each pass of which requires N/prime(i) actions, that is N/2 actions for 2, N/3 for 3 and so on; the summation of 1/p(i) for i = 1 to n, such that p(n + 1)**2 > N. The summation of 1/p(i) has been studied (by Hardie, I recall), but I lack the reference just now. Whichever, the action count is proportional to N*(summation of 1/p(i)), or N*(something that increases with N), which is clearly more than linear.

Supposing that multiplication and addition take about the same time (analysis of the processes say they have the same complexity, but offer little advice on methods to perform the processes), accordingly, for ever larger N, the multiplicative generation of composite numbers should eventually outrun the additive generation with redundancy. NickyMcLean 22:13, 18 June 2006 (UTC)

Apart from the computational advantaages of a "zero redundant exclusions" prime sieve; which remain to be established. There is the theoretical possibility that such a sieve could be used to establish an expression for the number of compound numbers less than n; and hense the number of primes less than n, say p; from p = n - c;regards rhnmcl