This is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |
Archive 1 | Archive 2 | Archive 3 |
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
--
Ausples
22:46, 14 May 2007 (UTC)
The following algorithm/code has runtime of Big-O(N−P). This means the range we are checking for prime numbers minus the number of primes found (there are no calculations for finding a prime number here, only true/false checks, primality was determined based on previous factors).
In computer science you can use boolean conditions to create the Sieve of Eratosthenes that runs sub-linear Big-O(N-P), by using a boolean memory location for each prime number in N, as follows:
O(100000000);
private void O(int N) { //<-- start copy.
int S = N; int p = 0; //this will always be a prime number only. Pre-Deterministic. int d = 0; //this will always be a factor of a prime number only. Deterministic. bool[] primeCheck = new bool[S]; //create a boolean array for the length to be checked for primes 0->N. for (p=2; p<S; p++) { switch(primeCheck[p]) { case true: continue; case false: { for (d=p+p; d < S; d+=p) { switch(primeCheck[d]) { case true: continue; case false: primeCheck[d] = true; break; } } //trace(p); //p will be the NEXT prime number. break; } } }
} //<-- end paste.
Functional closed circuit case.
Closed Circuit Time Testing
6/01/2006 4:19:20 PM
Scope(O): 100,000,000
Primes Found(P): 5,761,455
Memory Operations(N): 94,238,545 (Actual CPU runtime operations) (Time Complexity. Processor memory operations)
Time(Actual):
hours:0
minutes:0
seconds:10
milliseconds:843
6/01/2006 4:19:31 PM
As you can see, the code finds 5.7 million primes in 100 million possible choices in N-P operations. Always.
This code means that it is possible to run the Sieve of Eratosthenes in sub-linear Big-O(N-P) operations on a computer without factoring. Modifying the "for" loops to skip 2's does not improve the time complexity, nor does it improve the speed of the actual runtime.
At first glance, it would seem this algorithm is of complexity Big-O(N^2) or simply N^2, as they are nested loops. However, the sieve logic predetermines what the computer will or will not operate on at runtime. The computer algorithm will only operate on memory once for each location and does not operate on prime locations (but may optionally output at runtime). This gives us a sub-linear Big-O(N-P) where 0->N is the range the computer will check for primes, and P is the number of prime locations visited. This algorithm is of course restricted to finding primes in the range 0->N, where N can be as large as the maximum array size allowable by the compiler of your choice. There is no math in this code. We are not factoring primes here. They are fully determined during runtime. Big-O encapsulates the time complexity of loop control and conditional structures used for any program, as they are constants.
We use control structures to determine true/false conditions in the boolean array to determine a prime location based on when the memory is checked, which are constants for Big-O notation. Since we are concerned with primes, we are concerned with location rules, just like calculus, which is always represented as a straight line, for a polynomial equation. In this case, the above code appears to be N^2, but further examination of loop structure, control structure and runtime mapping prove complexity Big-O(N-P). The rules of the Sieve of Eratosthenes can be found in this article from Wichita State University's Math and Statistics department and the National Institue of Standards and Technology, respectively ->->
[1],
[2]. We determine prime locations in range 0->N by marking all non-primes using the inner loop, then visiting the next prime using the outer loop (which will be predetermined), then repeating until we reach N. This is sub-linear by virtue that P is not a constant. If P were a constant, then the time complexity would be Big-O(N). Above it is Big-O(N-P). There is no log N here. We always know that the algorithm will produce the same results each time for infinite N. There is no guess work, or modulus factoring.
Bibliography:
A1. Computer Science: An Overview by J. Glenn Brookshear, 1997 Addison Wesley publishing company. 0.3 The Evolution of Computer Science, p. 9 (Conceptual Theory)
B1. The World Treasury of Physics, Astronomy, and Mathematics: Edited by Timothy Ferris, Time Warner Book Group. Part Three: The Cosmos of Numbers::Artificial Intelligence and All That:::”The Computer and the Brain” by John Von Neuman 1958. p.483. (Full excerpt: p478-491) (Application Theory)
B2. The World Treasury of Physics, Astronomy, and Mathematics: Edited by Timothy Ferris, Time Warner Book Group. Part Three: The Cosmos of Numbers::Artificial Intelligence and All That:::”Can a Machine Think?” by Alan Turning ~1950. p.495-496. (Full excerpt: p492-519) (Application Theory)
C1. Algorithmics: The Spirit of Computing by David Harel, 1987~1996 Addison Wesley publishing company. 6.3 Order of Magnitude Improvements. p. 130-131. (Conceptual Theory)
D1. The Elegant Universe: Superstrings, Hidden Dimensions, and the Quest for the Ultimate Theory by Brian Greene, 1999 Vintage Books. The Super In Superstrings. p. 166,167 (System~Model Conceptual Theory)
Keep in mind this is a clever computer science solution, not a conventional one. --
Ausples
16:04, 11 May 2007 (UTC)
Comments by Ausples in PrimeHunter's comments removed by Ausples. Sorry about that. Won't happen again. :-) -- Ausples 21:52, 14 May 2007 (UTC)
The coded algorithm does not operate on prime number locations, therefore, it runs Big-O(N-P). As above. We do not know until the end of N how many exist in P, so P is not a constant. P is different for each N, therefore it's not constant. If it were, we could concede this to be Big-O(N). If it moves faster than N, but the variable P is not known until the end of runtime, the algorithm time complexity is reduced by the factor P, so it must run at Big-O(N-P), which is less than linear for some factor which equals the total number of primes found in N. How do we say that in Mathematics? Is that not sub-linear? Also, we're not concerned with the physical time results. Only that it runs algorithmically in Big-O(N-P). This also prevents overworking your processors and wear on the memory chips by not operating on them so much. :-/ --
Ausples
17:24, 11 May 2007 (UTC)
You can test how many memory operations by incrementing a counter, once after a line of code that sets a value in memory. e.g. "x=3". or in the case above, "primeCheck[d] = true". Although, intereseting to note: Asymptotic Time Complexity-The limiting behavior of the execution time of an algorithm when the size of the problem goes to infinity. This is usually expressed in Big-O notation ->
[3].
So then based on
Computational_complexity_theory.
This algorithm would have following complexities:
Time Complexity: Big-O(N-P) ~Here we are using memory operations time. Conditional operators are not expressed in Big-O time complexity. That is a technological limitation, not an algorithmic one.
Note1: The "continue" statement forces the processor to move on before any operations occur.
Note2: There is no known equation that produces primes, because it's exclusively an algorithm (thus a computer science problem). This can only be accomplished through an computer algorithm, following the instructions of the algorithm designer. This is exclusively a Sieve of Eratosthenes.
[4],
[5]
Note 3: The algorithm starts slow (it marks the smallest prime along N before visiting the next prime) but gets faster as P gets bigger. At N/2 it has finished checking off non-primes and only visits prime locations. So log(log N) does not apply for the duration of the algorithm, if it ever did. It still gets done in N-P operations. So for N=100,000,000 it will take the time it takes the processor to operate on N-P bits of memory (for Big-O(N-P)) but there will also be constant time for the control structures (which again are not expressed in the notation.
[6],
[7],
[8]).
--
Ausples
18:38, 11 May 2007 (UTC)
A1. Computer Science: An Overview by J. Glenn Brookshear, 1997 Addison Wesley publishing company. 0.3 The Evolution of Computer Science, p. 9 (Conceptual Theory)
C1. Algorithmics: The Spirit of Computing by David Harel, 1987~1996 Addison Wesley publishing company. 6.3 Order of Magnitude Improvements. p. 130-131. (Conceptual Theory)
The Sieve of Eratosthenes is an NP complete problem.
[10] so far, this is the only known sieve that satisfies the computer science definition for time complexity as per references above in N. Could another computer scientist explain further? Or explain why this is not Big-O(N-P) algorithm time complexity based on computer science, not in math? This isn't just a math problem. Math just claims it, but still can't solve it in N. We want it back. This is OUR Sieve of Eratosthenes.
--
Ausples
01:38, 12 May 2007 (UTC)
The statement->"One could not apply the current conventional rules to this algorithm"--retracted. You can certainly apply conventional computer science rules here, as this algorithm follows those standards (see above references). Prime Hunter wrote: "I can say with confidence that Ausples' implementation is relatively slow in actual running time compared to many other implementations." Again, this does not matter for Big-O notation. Again, this is a technological limitation, not an algorithmic one. Big-O(N-P) does not change from computer to computer. But here is some hard data from my system:
The processor speed is really arbitrary here. It could be done with a 1MHz processor, it's still going to come out as Big-O(N-P)). You will want to plot starting at N=1,000,000(1M) as the computer does not spend any actual time in milliseconds finding primes until N=1,000,000. (And apparently finds 1,624,528 primes when N=26,000,0000 in about 2 and a half seconds on my system. At higher ranges, it still runs Big-O(N-P))
|N (range 0->N)| | |Time in Milliseconds| | |Primes Found| | |Total Processor Memory Operations (N-P)| |
1000 | 0 | 169 | 830 |
10000 | 0 | 1230 | 8769 |
100000 | 0 | 9593 | 90406 |
1000000 | 46 | 78499 | 921500 |
2000000 | 171 | 148934 | 1851065 |
3000000 | 265 | 216817 | 2783182 |
4000000 | 343 | 283147 | 3716852 |
5000000 | 484 | 348514 | 4651485 |
6000000 | 562 | 412850 | 5587149 |
7000000 | 656 | 476649 | 6523350 |
8000000 | 750 | 539778 | 7460221 |
9000000 | 906 | 602490 | 8397509 |
10000000 | 921 | 664580 | 9335419 |
11000000 | 1015 | 726518 | 10273481 |
12000000 | 1156 | 788061 | 11211938 |
13000000 | 1250 | 849253 | 12150746 |
14000000 | 1406 | 910078 | 13089921 |
15000000 | 1468 | 970705 | 14029294 |
16000000 | 1578 | 1031131 | 14968868 |
17000000 | 1671 | 1091315 | 15908684 |
18000000 | 1718 | 1151368 | 16848631 |
19000000 | 1859 | 1211051 | 17788948 |
20000000 | 1921 | 1270608 | 18729391 |
21000000 | 2015 | 1329944 | 19670055 |
22000000 | 2140 | 1389262 | 20610737 |
23000000 | 2234 | 1448222 | 21551777 |
24000000 | 2375 | 1507123 | 22492876 |
25000000 | 2421 | 1565928 | 23432071 |
26000000 | 2531 | 1624528 | 24375471 |
and on and on |
You can get more results for 100M->1xxM and the result will be the same. Linear.
Slight millisecond variances (if any) are due to OS restrictions on processor time for multi-threading OS background tasks. This is common on popular operating systems. You can test this up to the limit the OS will allocate for a boolean array. It will still be a linear result. I can draw the graph for you, or you can plot it in a spreadsheet yourself. Big-O(N-P). Actual runtime indicates it, actual operation count proves it. The graph is a straight line. There is no logN anywhere in the above code. Please provide references for your refutation, otherwise this cannot be challenged. I do not understand terms like: "I think", "I believe", "I feel", they are not academic terms. Please break down the time complexity using computer science based references. This has been done by myself throughout this discussion. Where is your reference for refutation? If I were to "believe", I believe that this is what Eratosthenes had in mind, since it runs O(N-P) to the computer, and matches exactly his user requirements. [19], [20] -- Ausples 13:35, 13 May 2007 (UTC)
Please provide references. Further, no breaks need be removed from this code. The last break belongs to the false case in the first switch statement, this is not a bug. In N=100M (as you claim above producing primes in .47 seconds), we compute that around ~10 seconds using the code above, not 3.4 seconds. Actual time is a technological limitation, not an algorithmic one, therefore arbitrary to Big-O time complexity. What is important is that over several controlled tests that the algorithm produces Big-O(N-P). You are also claiming that your algorithm would go faster than the above mentioned "square sieve", (or the quadratic sieve for that matter) cited in that masters level artificial intelligence class -> [23] . Call me skeptical on that note. ;-) If you do not provide references for these claims, they must be false because they would then be based in ego("I"), not reality. We are made to "believe", which again is not academic, even less scientific. Further, if the code above is not producing prime numbers at runtime, then what is it doing? That trace line is a console output. "p" is always a prime number in this algorithm. This can be proven by adding the console output line. Which, was apparently not done, as Prime Hunter says, "but it's not the Sieve of Eratosthenes, and it does not compute primes." Right, it's determinisitic; the outer loop knows that the next location it visits will be a prime location. And it does in fact meet the user requirements set out by Eratosthenes [24], [25]. We covered that. But at least we agree it runs Big-O(N-P). As for your citation above, this applies outside the scope of this article in "factoring" primes. The Sieve of Eratosthenes is concerned with the NEXT prime, not factoring them. Read the requirements again [26], [27], and use a historical context this time. There is no mention of factoring anywhere. It's all about how you get to the NEXT prime (last I checked in calculus, a prime is a derivative location represented by a linear slope for an equation.). This is not a matter of agreeing. This is the Sieve of Eratosthenes as per user requirements [28], [29] . It is a hard fact.-- Ausples 20:02, 13 May 2007 (UTC)
Thank you for your references PH. It seems there was a copy/paste error. You can now copy/paste the code block, and modify data types as necessary. The output will be correct(as long as the datatypes are equivalent). Now you can see the alignment more clearly (all braces have end braces). And of course, there are now copy/paste instructions. I'm not quite sure why the code would stream those values, but the code block above is currently producing 2 3 5 7 11 13 17 19 23 -> N. Not sure why you would get that sequence you're referring to. If it was missing a brace, it shouldn't even have compiled. But thanks for trying to fix it... It's fine now. Thanks again for the feedback. One may copy/paste the block again. And no, we cannot add the article at this time. It must remain in discussion for now. :-| -- Ausples 19:17, 14 May 2007 (UTC)
Hi everyone,
The order of the entire algorithm is O(N * N / ln(N)).
The outer loop executes once. During its execution, it repeats O(N) times.
The inner loop executes for each prime found. From the prime number theorem, there will be O(N/ln(N)) primes in the range, 0..N.
Each time the inner loop executes, it repeats O(N) times.
Each repeat of the inner loop takes O(1).
-- Kevinkor2 15:00, 15 May 2007 (UTC)
The animation (in rectangular form) is nominated to become a Featured Picture, see Wikipedia:Featured picture candidates/Sieve of Eratosthenes. I said there that animation should be changed so that, when crossing off multiples of p, it starts at 2p instead of p2. I think the current animation, which starts at p2, will confuse some readers (see also the comments at the featured picture candidates page), and it is not an essential part of the algorithm to start at p2 (it does not change the N log log N complexity). However, I'm not sure about the latter bit, so please correct me if I'm wrong. -- Jitse Niesen ( talk) 01:59, 26 September 2007 (UTC)
Your opinions are invited on this graphic view of Eratosthenes sieve. Cuddlyable3 20:42, 8 September 2007 (UTC)
Is the second image better? Cuddlyable3 16:43, 19 September 2007 (UTC)
Features of the latest animation:
-- is a way of suggesting that the domain of composite and prime numbers is unlimited i.e. not an intrinsic limit of the algorithm
-- avoids emphasizing any particular multiples, which all rectangular tables are bound to do
-- contrasts the regularity of the natural numbers with the irregularity of the prime numbers. Cuddlyable3 19:39, 25 September 2007 (UTC)
Is it just me that finds animated pictures in articles really annoying? How can you read an article if there's something jumping around on the screen at the same time? I'd much prefer a link to an animated visualization. 78.52.193.99 ( talk) 09:47, 24 March 2008 (UTC)
When thinking of a way to implement this in Haskell, which is done with respect to lists rather than a procedural algorithm, it seems to me that it would be easier to describe this as the list of numbers is iterated over and each prime before it would be tested as a factor rather than all numbers before it.
FlowRate ( talk) 03:00, 27 June 2008 (UTC)
I like the animation but I think it would be even better if the column width was 6 as opposed to 10. The multiples of 2, 3, 5 and 7 all make really simple patterns that way. Just my opinion... i'm sure there are others who wouldn't want to sacrifice any "digitalness". —Preceding unsigned comment added by 90.207.204.55 ( talk) 04:28, 21 December 2008 (UTC)
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
—Preceding unsigned comment added by Rhnmcl ( talk • contribs)
For more discussion on this algoritm see Talk:Sieve_of_Eratosthenes#Euler's sieve Zfishwiki ( talk) 00:15, 3 April 2009 (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} —Preceding unsigned comment added by Rhnmcl ( talk • contribs)
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...
I've made a new gif for this page based on some comments stated here: Wikipedia:Featured picture candidates/Sieve of Eratosthenes. Should the old one be replaced with this one? Improvements:
Note: I'm quite new. I do my best to do everything roughly right, but there's lots of guidelines to adhere to. If I did anything wrong, just poke me in the right direction. Thanks :) M.qrius ( talk) 22:25, 27 December 2007 (UTC) Hi, That is a fantastic GIF picture!But yours is not as pretty as the old one,I am afraid.How do you make these pictures,can you tell me? I want to make some myself Visame ( talk) 18:38, 3 May 2008 (UTC)
I actually rather like this animation. Somebody should seriously consider replacing the front-page animation with it, or something mighty similar. I do think it's a lot more clear. Maybe not quite as pretty and refined, but it's adequate, and certainly more utilitarian.
Looking at it again, in comparison to the original that it's based on, you seem to have rather large margins around the list of primes to the right. These could probably be reduced a bit
Obscuranym ( talk) 18:49, 10 March 2009 (UTC)
I think it should be noted that (of course depending on the abstract machine used for complexity analysis) the time complexity is in fact , because the size of the presentation of is , and therefore an addition takes time. Morgurth ( talk) 14:30, 3 December 2008 (UTC)
The article says, "It works efficiently for the smaller primes (below 10 million) [2].", but the source says, "The most efficient way to find all of the small primes (say all those less than 10,000,000)" I think what The Prime Glossary is saying is that Eratosthenes is the most efficient way to find all the primes between 2 and any n (i.e. the smallest primes, with some barrier). 10 million was just an example, while Eratosthenes is always fastest for this task when starting from scratch. I don't know of some better algorithm for finding e.g. all primes from 2 to 1 googol (again, assuming you have no information when starting). Superm401 - Talk 12:39, 2 January 2009 (UTC)
"Sift the Two's and sift the Three's" is dead wrong. Never use an apostrophe in a plural. Why can't we correct the terrible punctuation of the source? The source isn't even the original source of the poem. It's just a poem and is not presented as a quote. You can't misquote something attributed to anonymous. These sources have the poem properly written: [34] [35]. Reywas92 Talk 01:54, 26 March 2009 (UTC)
The poem doesn't "replicate the essence" of the sieve. "Replicate" suggests it somehow follows the same process, which it certainly doesn't (it would be cleverer if it did). Neither does it describe anything that could reasonably be called the essence of the algorithm. It merely gives a vague idea of the process that's recognizable if you are familiar with the sieve. The description in the article sounds like unnecessary verbiage. 85.181.121.175 ( talk) 11:34, 28 April 2009 (UTC)
Euler in his Proof of the Euler product formula for the Riemann zeta function came up with a better version of the sieve of eratosthenes in which each number was eliminated exactly once.
This runs as follows. We start with the sequence of natural numbers
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35...
we then multiply each member of this sequence by two and remove from the original sequence to obtain
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35...
we then multiply each member of this sequence by three and remove from the working sequence to obtain
1 5 7 11 13 17 19 23 25 29 31 35...
we then multiply each member of this sequence by five (the first number after one) and remove from the working sequence to obtain
1 7 11 13 17 19 23 29 31 ...
Each member of the working sequence we remove is removed exactly once unlike the original Eratosthenes algorithm. If we continue with this process indefinately we will be left with just the number one in our working sequence, as in the Proof of the Euler product formula for the Riemann zeta function.
If however we store the eliminated prime numbers as they arrive in a queue and combine them with the working sequence when we have exceeded the square root of the upper limit of our range, we have the desired sequence of prime numbers. Of course we must also eliminate the remaining number one in our working sequence.
Zfishwiki ( talk) 00:08, 3 April 2009 (UTC)
This algorithm is I believe essentially equivalent to that described in Talk:Sieve_of_Eratosthenes#"A Reduced Redundant Exclusions (RRE) Prime Sieve", except that primes as they are discovered are now eliminated from the working sequence. However where that counted as new research, my algorithm is based on the Proof of the Euler product formula for the Riemann zeta function. I have therefore stuck as closely to Euler's algorithm as closely as possible
Please let me know whether this should be included in the original article. If so I think we should delete the reference to starting with the square of the working prime when eliminating further composite numbers, as although increasing the efficiency of the algorithm, it does not do so as efficiently as the algorithm here described does.
Zfishwiki ( talk) 00:08, 3 April 2009 (UTC)
Okay I have taken it upon myself to add this section to the article, in the absence of any discussion of it after seven days. My reason's for doing so are -:
Zfishwiki ( talk) 23:32, 9 April 2009 (UTC)
I disagree. I have described the algorithm in ordinary language which is easy to understand, rather than be excessively formal. I believe most people would understand that when I said we eliminate the prime numbers as they arrive and store them in in a queue, the number two would be included in this queue.
The first stage of the algorithm is to multiply the sequence by two (the first number after one to be explicit) and remove these numbers from the original sequence. I fail to see how this is any different from my treatment of the primes three and five. Common sense would indicate that it is to be treated in the same manner.
If I were to define my argument in a more exact fashion I believe this would reduce its readability and thus the value of the article.
Zfishwiki ( talk) 18:50, 24 June 2009 (UTC)
If you think you can explain the algorithm more simply, feel free to make the change. However I have taken a lot of care in my explanation and you might find it is harder than you think to improve it.
There is a good reason for including 1 in the working sequence. For example when we multiply by 3, this ensures that 3 is present in the multiplied sequence, and thus 3 is then eliminated from the working sequence. If 1 was not present in the working sequence, 3 would not be eliminated and we would have to complicate the algorithm by introducing some rule to eliminate 3. It is just more elegant mathematically to have the 1 constantly present.
I say towards the end of the algorithm that primes as they are eliminated are stored in a queue and this would include 2, most people know that 2 is a prime number, and 2 is therefore the first prime to be stored in a queue. I could explicitly say that each time we multiply the working sequence by a number, then that number is prime and is then stored in a queue. If it makes you happy go ahead and make that change.
Zfishwiki ( talk) 13:31, 25 June 2009 (UTC)
I have altered the final paragraph to explicitly say which numbers are to be stored in a queue, and how they are to be combined with the final working sequence. Hope this satisfies your concern.
Zfishwiki ( talk) 14:08, 25 June 2009 (UTC)
I have also labelled the primes as they arrive in the example, to avoid any possible confusion. In my opinion this makes the description of the algorithm more fussy, but that is just my opinion.
Zfishwiki ( talk) 14:29, 25 June 2009 (UTC)
A) Start with all the natural numbers except '1' that is not a prime. 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35... ^ B) The leftmost number is prime. Multiply each number in the list by this prime and discard the products. 2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35... ^ C) The number after the previous prime is also a prime. Multiply each number in the list starting from the latest prime by the latest prime and discard the products. 2 3 5 7 11 13 17 19 23 25 27 29 31 35... ^ Repeat C) indefinitely. On each repetition a new prime is identified (marked ^) until all the primes in the starting list have been found.
Cuddlyable3 ( talk) 20:40, 25 June 2009 (UTC)
Well this seems to be equivalent to my algorithm, although it does not stick as close to Euler's proof of the product identity, so could be construed as original research. Go ahead and make the change if it makes you happy.
Zfishwiki ( talk) 10:34, 26 June 2009 (UTC)
Done. Cuddlyable3 ( talk) 12:44, 26 June 2009 (UTC)
In Euler's proof we have a mathematical series on the right hand side, and we sift the series in waves until the right hand side consists solely of the term 1. We then rearrange the equation to get the product identity.
I have removed the statement that we are left with a sequence of primes in Euler's proof . If you want to explain how the algorithm relates to Euler's proof, I suggest you say that the primes to the left of the cursor correspond to factors on the left hand side of the equation at each stage, whereas the sequence to the right of the cursor corresponds to the series on the right hand of the equation.
Zfishwiki ( talk) 16:45, 26 June 2009 (UTC)
Okay I've made these changes.
Zfishwiki ( talk) 17:21, 26 June 2009 (UTC)
The article says that Euler's algorithm is better. It does not say why. It does not give the running time of Euler's algorithm, nor the storage requirement. There is also no specification of the algorithm in pseudo-code. I appreciate that an algorithm is mentioned here that is often not mentioned in discussions about the Sieve of Eratosthenes, but this section would be a lot more useful with the aforementioned information. - ATBS 15Aug09 —Preceding unsigned comment added by 71.112.25.123 ( talk) 11:13, 16 August 2009 (UTC)
I am not sure I agree with the present expansion of the explanation of Euler's algorithm. Whilst the former explanation was probably too concise, the present one is too unwieldly. There is no need to calculate all the multiples at each stage; we can stop when we have exceeded the upper range, and therefore we only need to print the preformatted multiple list up to the upper range in our description.
I won't make this change because I prefer the description given at the top of this section, which is closer to Euler's proof of his identity. I'll leave it to someone else to make the change if he wants to!
Zfishwiki ( talk) 00:45, 30 November 2009 (UTC)
From the description I get the idea that Euler's Sieve only remove's numbers that are the factor of 2 primes. For instance if I understood correctly then on the first run we remove the multiples of 2, then the multiples of 3 (which removes 9 because 3*3 = 9). Then we remove all the multiples of 5, 5*5 = 25, 5*7 = 35, 5*11 = 55 ... we have missed 45.
Please correct me if I'm wrong and remove the disputed notice I've attached. Thanks Genjix ( talk) 18:41, 22 June 2010 (UTC)
It's possible to view the positive integers as the vertices on a directed tree where the edges are multiplication by prime numbers. This implementation is typically slower than the sieve of eratosthenes, but it is very easy to adapt it to calculate phi and other functions : -- Nic Roets ( talk) 23:14, 11 May 2010 (UTC)
#define pmaks 1000000
int ppmaks/10], foundpmaks], i, j = 0;
void S (int k, int n)
{
int l;
foundn = 1;
for (l = 0; pl * n < pmaks && l <= k; l++) S (l, n * pl]);
}
int main ()
{
memset (found, 0, sizeof (found));
for (i = 2; i < pmaks; i++) {
if (!foundi]) {
pj = i;
S (j++, i);
printf ("%d\n", i);
}
}
}
I believe the algorithm shown in C is an implementation of Eratosthenes' sieve, not Euler's sieve. It visits each multiple of each prime found, not only the products of the prime with values still left in the list. However, it is listed under the section for Euler's sieve, which is misleading. -- 76.191.195.184 ( talk) 23:19, 26 December 2010 (UTC)
This is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |
Archive 1 | Archive 2 | Archive 3 |
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
--
Ausples
22:46, 14 May 2007 (UTC)
The following algorithm/code has runtime of Big-O(N−P). This means the range we are checking for prime numbers minus the number of primes found (there are no calculations for finding a prime number here, only true/false checks, primality was determined based on previous factors).
In computer science you can use boolean conditions to create the Sieve of Eratosthenes that runs sub-linear Big-O(N-P), by using a boolean memory location for each prime number in N, as follows:
O(100000000);
private void O(int N) { //<-- start copy.
int S = N; int p = 0; //this will always be a prime number only. Pre-Deterministic. int d = 0; //this will always be a factor of a prime number only. Deterministic. bool[] primeCheck = new bool[S]; //create a boolean array for the length to be checked for primes 0->N. for (p=2; p<S; p++) { switch(primeCheck[p]) { case true: continue; case false: { for (d=p+p; d < S; d+=p) { switch(primeCheck[d]) { case true: continue; case false: primeCheck[d] = true; break; } } //trace(p); //p will be the NEXT prime number. break; } } }
} //<-- end paste.
Functional closed circuit case.
Closed Circuit Time Testing
6/01/2006 4:19:20 PM
Scope(O): 100,000,000
Primes Found(P): 5,761,455
Memory Operations(N): 94,238,545 (Actual CPU runtime operations) (Time Complexity. Processor memory operations)
Time(Actual):
hours:0
minutes:0
seconds:10
milliseconds:843
6/01/2006 4:19:31 PM
As you can see, the code finds 5.7 million primes in 100 million possible choices in N-P operations. Always.
This code means that it is possible to run the Sieve of Eratosthenes in sub-linear Big-O(N-P) operations on a computer without factoring. Modifying the "for" loops to skip 2's does not improve the time complexity, nor does it improve the speed of the actual runtime.
At first glance, it would seem this algorithm is of complexity Big-O(N^2) or simply N^2, as they are nested loops. However, the sieve logic predetermines what the computer will or will not operate on at runtime. The computer algorithm will only operate on memory once for each location and does not operate on prime locations (but may optionally output at runtime). This gives us a sub-linear Big-O(N-P) where 0->N is the range the computer will check for primes, and P is the number of prime locations visited. This algorithm is of course restricted to finding primes in the range 0->N, where N can be as large as the maximum array size allowable by the compiler of your choice. There is no math in this code. We are not factoring primes here. They are fully determined during runtime. Big-O encapsulates the time complexity of loop control and conditional structures used for any program, as they are constants.
We use control structures to determine true/false conditions in the boolean array to determine a prime location based on when the memory is checked, which are constants for Big-O notation. Since we are concerned with primes, we are concerned with location rules, just like calculus, which is always represented as a straight line, for a polynomial equation. In this case, the above code appears to be N^2, but further examination of loop structure, control structure and runtime mapping prove complexity Big-O(N-P). The rules of the Sieve of Eratosthenes can be found in this article from Wichita State University's Math and Statistics department and the National Institue of Standards and Technology, respectively ->->
[1],
[2]. We determine prime locations in range 0->N by marking all non-primes using the inner loop, then visiting the next prime using the outer loop (which will be predetermined), then repeating until we reach N. This is sub-linear by virtue that P is not a constant. If P were a constant, then the time complexity would be Big-O(N). Above it is Big-O(N-P). There is no log N here. We always know that the algorithm will produce the same results each time for infinite N. There is no guess work, or modulus factoring.
Bibliography:
A1. Computer Science: An Overview by J. Glenn Brookshear, 1997 Addison Wesley publishing company. 0.3 The Evolution of Computer Science, p. 9 (Conceptual Theory)
B1. The World Treasury of Physics, Astronomy, and Mathematics: Edited by Timothy Ferris, Time Warner Book Group. Part Three: The Cosmos of Numbers::Artificial Intelligence and All That:::”The Computer and the Brain” by John Von Neuman 1958. p.483. (Full excerpt: p478-491) (Application Theory)
B2. The World Treasury of Physics, Astronomy, and Mathematics: Edited by Timothy Ferris, Time Warner Book Group. Part Three: The Cosmos of Numbers::Artificial Intelligence and All That:::”Can a Machine Think?” by Alan Turning ~1950. p.495-496. (Full excerpt: p492-519) (Application Theory)
C1. Algorithmics: The Spirit of Computing by David Harel, 1987~1996 Addison Wesley publishing company. 6.3 Order of Magnitude Improvements. p. 130-131. (Conceptual Theory)
D1. The Elegant Universe: Superstrings, Hidden Dimensions, and the Quest for the Ultimate Theory by Brian Greene, 1999 Vintage Books. The Super In Superstrings. p. 166,167 (System~Model Conceptual Theory)
Keep in mind this is a clever computer science solution, not a conventional one. --
Ausples
16:04, 11 May 2007 (UTC)
Comments by Ausples in PrimeHunter's comments removed by Ausples. Sorry about that. Won't happen again. :-) -- Ausples 21:52, 14 May 2007 (UTC)
The coded algorithm does not operate on prime number locations, therefore, it runs Big-O(N-P). As above. We do not know until the end of N how many exist in P, so P is not a constant. P is different for each N, therefore it's not constant. If it were, we could concede this to be Big-O(N). If it moves faster than N, but the variable P is not known until the end of runtime, the algorithm time complexity is reduced by the factor P, so it must run at Big-O(N-P), which is less than linear for some factor which equals the total number of primes found in N. How do we say that in Mathematics? Is that not sub-linear? Also, we're not concerned with the physical time results. Only that it runs algorithmically in Big-O(N-P). This also prevents overworking your processors and wear on the memory chips by not operating on them so much. :-/ --
Ausples
17:24, 11 May 2007 (UTC)
You can test how many memory operations by incrementing a counter, once after a line of code that sets a value in memory. e.g. "x=3". or in the case above, "primeCheck[d] = true". Although, intereseting to note: Asymptotic Time Complexity-The limiting behavior of the execution time of an algorithm when the size of the problem goes to infinity. This is usually expressed in Big-O notation ->
[3].
So then based on
Computational_complexity_theory.
This algorithm would have following complexities:
Time Complexity: Big-O(N-P) ~Here we are using memory operations time. Conditional operators are not expressed in Big-O time complexity. That is a technological limitation, not an algorithmic one.
Note1: The "continue" statement forces the processor to move on before any operations occur.
Note2: There is no known equation that produces primes, because it's exclusively an algorithm (thus a computer science problem). This can only be accomplished through an computer algorithm, following the instructions of the algorithm designer. This is exclusively a Sieve of Eratosthenes.
[4],
[5]
Note 3: The algorithm starts slow (it marks the smallest prime along N before visiting the next prime) but gets faster as P gets bigger. At N/2 it has finished checking off non-primes and only visits prime locations. So log(log N) does not apply for the duration of the algorithm, if it ever did. It still gets done in N-P operations. So for N=100,000,000 it will take the time it takes the processor to operate on N-P bits of memory (for Big-O(N-P)) but there will also be constant time for the control structures (which again are not expressed in the notation.
[6],
[7],
[8]).
--
Ausples
18:38, 11 May 2007 (UTC)
A1. Computer Science: An Overview by J. Glenn Brookshear, 1997 Addison Wesley publishing company. 0.3 The Evolution of Computer Science, p. 9 (Conceptual Theory)
C1. Algorithmics: The Spirit of Computing by David Harel, 1987~1996 Addison Wesley publishing company. 6.3 Order of Magnitude Improvements. p. 130-131. (Conceptual Theory)
The Sieve of Eratosthenes is an NP complete problem.
[10] so far, this is the only known sieve that satisfies the computer science definition for time complexity as per references above in N. Could another computer scientist explain further? Or explain why this is not Big-O(N-P) algorithm time complexity based on computer science, not in math? This isn't just a math problem. Math just claims it, but still can't solve it in N. We want it back. This is OUR Sieve of Eratosthenes.
--
Ausples
01:38, 12 May 2007 (UTC)
The statement->"One could not apply the current conventional rules to this algorithm"--retracted. You can certainly apply conventional computer science rules here, as this algorithm follows those standards (see above references). Prime Hunter wrote: "I can say with confidence that Ausples' implementation is relatively slow in actual running time compared to many other implementations." Again, this does not matter for Big-O notation. Again, this is a technological limitation, not an algorithmic one. Big-O(N-P) does not change from computer to computer. But here is some hard data from my system:
The processor speed is really arbitrary here. It could be done with a 1MHz processor, it's still going to come out as Big-O(N-P)). You will want to plot starting at N=1,000,000(1M) as the computer does not spend any actual time in milliseconds finding primes until N=1,000,000. (And apparently finds 1,624,528 primes when N=26,000,0000 in about 2 and a half seconds on my system. At higher ranges, it still runs Big-O(N-P))
|N (range 0->N)| | |Time in Milliseconds| | |Primes Found| | |Total Processor Memory Operations (N-P)| |
1000 | 0 | 169 | 830 |
10000 | 0 | 1230 | 8769 |
100000 | 0 | 9593 | 90406 |
1000000 | 46 | 78499 | 921500 |
2000000 | 171 | 148934 | 1851065 |
3000000 | 265 | 216817 | 2783182 |
4000000 | 343 | 283147 | 3716852 |
5000000 | 484 | 348514 | 4651485 |
6000000 | 562 | 412850 | 5587149 |
7000000 | 656 | 476649 | 6523350 |
8000000 | 750 | 539778 | 7460221 |
9000000 | 906 | 602490 | 8397509 |
10000000 | 921 | 664580 | 9335419 |
11000000 | 1015 | 726518 | 10273481 |
12000000 | 1156 | 788061 | 11211938 |
13000000 | 1250 | 849253 | 12150746 |
14000000 | 1406 | 910078 | 13089921 |
15000000 | 1468 | 970705 | 14029294 |
16000000 | 1578 | 1031131 | 14968868 |
17000000 | 1671 | 1091315 | 15908684 |
18000000 | 1718 | 1151368 | 16848631 |
19000000 | 1859 | 1211051 | 17788948 |
20000000 | 1921 | 1270608 | 18729391 |
21000000 | 2015 | 1329944 | 19670055 |
22000000 | 2140 | 1389262 | 20610737 |
23000000 | 2234 | 1448222 | 21551777 |
24000000 | 2375 | 1507123 | 22492876 |
25000000 | 2421 | 1565928 | 23432071 |
26000000 | 2531 | 1624528 | 24375471 |
and on and on |
You can get more results for 100M->1xxM and the result will be the same. Linear.
Slight millisecond variances (if any) are due to OS restrictions on processor time for multi-threading OS background tasks. This is common on popular operating systems. You can test this up to the limit the OS will allocate for a boolean array. It will still be a linear result. I can draw the graph for you, or you can plot it in a spreadsheet yourself. Big-O(N-P). Actual runtime indicates it, actual operation count proves it. The graph is a straight line. There is no logN anywhere in the above code. Please provide references for your refutation, otherwise this cannot be challenged. I do not understand terms like: "I think", "I believe", "I feel", they are not academic terms. Please break down the time complexity using computer science based references. This has been done by myself throughout this discussion. Where is your reference for refutation? If I were to "believe", I believe that this is what Eratosthenes had in mind, since it runs O(N-P) to the computer, and matches exactly his user requirements. [19], [20] -- Ausples 13:35, 13 May 2007 (UTC)
Please provide references. Further, no breaks need be removed from this code. The last break belongs to the false case in the first switch statement, this is not a bug. In N=100M (as you claim above producing primes in .47 seconds), we compute that around ~10 seconds using the code above, not 3.4 seconds. Actual time is a technological limitation, not an algorithmic one, therefore arbitrary to Big-O time complexity. What is important is that over several controlled tests that the algorithm produces Big-O(N-P). You are also claiming that your algorithm would go faster than the above mentioned "square sieve", (or the quadratic sieve for that matter) cited in that masters level artificial intelligence class -> [23] . Call me skeptical on that note. ;-) If you do not provide references for these claims, they must be false because they would then be based in ego("I"), not reality. We are made to "believe", which again is not academic, even less scientific. Further, if the code above is not producing prime numbers at runtime, then what is it doing? That trace line is a console output. "p" is always a prime number in this algorithm. This can be proven by adding the console output line. Which, was apparently not done, as Prime Hunter says, "but it's not the Sieve of Eratosthenes, and it does not compute primes." Right, it's determinisitic; the outer loop knows that the next location it visits will be a prime location. And it does in fact meet the user requirements set out by Eratosthenes [24], [25]. We covered that. But at least we agree it runs Big-O(N-P). As for your citation above, this applies outside the scope of this article in "factoring" primes. The Sieve of Eratosthenes is concerned with the NEXT prime, not factoring them. Read the requirements again [26], [27], and use a historical context this time. There is no mention of factoring anywhere. It's all about how you get to the NEXT prime (last I checked in calculus, a prime is a derivative location represented by a linear slope for an equation.). This is not a matter of agreeing. This is the Sieve of Eratosthenes as per user requirements [28], [29] . It is a hard fact.-- Ausples 20:02, 13 May 2007 (UTC)
Thank you for your references PH. It seems there was a copy/paste error. You can now copy/paste the code block, and modify data types as necessary. The output will be correct(as long as the datatypes are equivalent). Now you can see the alignment more clearly (all braces have end braces). And of course, there are now copy/paste instructions. I'm not quite sure why the code would stream those values, but the code block above is currently producing 2 3 5 7 11 13 17 19 23 -> N. Not sure why you would get that sequence you're referring to. If it was missing a brace, it shouldn't even have compiled. But thanks for trying to fix it... It's fine now. Thanks again for the feedback. One may copy/paste the block again. And no, we cannot add the article at this time. It must remain in discussion for now. :-| -- Ausples 19:17, 14 May 2007 (UTC)
Hi everyone,
The order of the entire algorithm is O(N * N / ln(N)).
The outer loop executes once. During its execution, it repeats O(N) times.
The inner loop executes for each prime found. From the prime number theorem, there will be O(N/ln(N)) primes in the range, 0..N.
Each time the inner loop executes, it repeats O(N) times.
Each repeat of the inner loop takes O(1).
-- Kevinkor2 15:00, 15 May 2007 (UTC)
The animation (in rectangular form) is nominated to become a Featured Picture, see Wikipedia:Featured picture candidates/Sieve of Eratosthenes. I said there that animation should be changed so that, when crossing off multiples of p, it starts at 2p instead of p2. I think the current animation, which starts at p2, will confuse some readers (see also the comments at the featured picture candidates page), and it is not an essential part of the algorithm to start at p2 (it does not change the N log log N complexity). However, I'm not sure about the latter bit, so please correct me if I'm wrong. -- Jitse Niesen ( talk) 01:59, 26 September 2007 (UTC)
Your opinions are invited on this graphic view of Eratosthenes sieve. Cuddlyable3 20:42, 8 September 2007 (UTC)
Is the second image better? Cuddlyable3 16:43, 19 September 2007 (UTC)
Features of the latest animation:
-- is a way of suggesting that the domain of composite and prime numbers is unlimited i.e. not an intrinsic limit of the algorithm
-- avoids emphasizing any particular multiples, which all rectangular tables are bound to do
-- contrasts the regularity of the natural numbers with the irregularity of the prime numbers. Cuddlyable3 19:39, 25 September 2007 (UTC)
Is it just me that finds animated pictures in articles really annoying? How can you read an article if there's something jumping around on the screen at the same time? I'd much prefer a link to an animated visualization. 78.52.193.99 ( talk) 09:47, 24 March 2008 (UTC)
When thinking of a way to implement this in Haskell, which is done with respect to lists rather than a procedural algorithm, it seems to me that it would be easier to describe this as the list of numbers is iterated over and each prime before it would be tested as a factor rather than all numbers before it.
FlowRate ( talk) 03:00, 27 June 2008 (UTC)
I like the animation but I think it would be even better if the column width was 6 as opposed to 10. The multiples of 2, 3, 5 and 7 all make really simple patterns that way. Just my opinion... i'm sure there are others who wouldn't want to sacrifice any "digitalness". —Preceding unsigned comment added by 90.207.204.55 ( talk) 04:28, 21 December 2008 (UTC)
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
—Preceding unsigned comment added by Rhnmcl ( talk • contribs)
For more discussion on this algoritm see Talk:Sieve_of_Eratosthenes#Euler's sieve Zfishwiki ( talk) 00:15, 3 April 2009 (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} —Preceding unsigned comment added by Rhnmcl ( talk • contribs)
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...
I've made a new gif for this page based on some comments stated here: Wikipedia:Featured picture candidates/Sieve of Eratosthenes. Should the old one be replaced with this one? Improvements:
Note: I'm quite new. I do my best to do everything roughly right, but there's lots of guidelines to adhere to. If I did anything wrong, just poke me in the right direction. Thanks :) M.qrius ( talk) 22:25, 27 December 2007 (UTC) Hi, That is a fantastic GIF picture!But yours is not as pretty as the old one,I am afraid.How do you make these pictures,can you tell me? I want to make some myself Visame ( talk) 18:38, 3 May 2008 (UTC)
I actually rather like this animation. Somebody should seriously consider replacing the front-page animation with it, or something mighty similar. I do think it's a lot more clear. Maybe not quite as pretty and refined, but it's adequate, and certainly more utilitarian.
Looking at it again, in comparison to the original that it's based on, you seem to have rather large margins around the list of primes to the right. These could probably be reduced a bit
Obscuranym ( talk) 18:49, 10 March 2009 (UTC)
I think it should be noted that (of course depending on the abstract machine used for complexity analysis) the time complexity is in fact , because the size of the presentation of is , and therefore an addition takes time. Morgurth ( talk) 14:30, 3 December 2008 (UTC)
The article says, "It works efficiently for the smaller primes (below 10 million) [2].", but the source says, "The most efficient way to find all of the small primes (say all those less than 10,000,000)" I think what The Prime Glossary is saying is that Eratosthenes is the most efficient way to find all the primes between 2 and any n (i.e. the smallest primes, with some barrier). 10 million was just an example, while Eratosthenes is always fastest for this task when starting from scratch. I don't know of some better algorithm for finding e.g. all primes from 2 to 1 googol (again, assuming you have no information when starting). Superm401 - Talk 12:39, 2 January 2009 (UTC)
"Sift the Two's and sift the Three's" is dead wrong. Never use an apostrophe in a plural. Why can't we correct the terrible punctuation of the source? The source isn't even the original source of the poem. It's just a poem and is not presented as a quote. You can't misquote something attributed to anonymous. These sources have the poem properly written: [34] [35]. Reywas92 Talk 01:54, 26 March 2009 (UTC)
The poem doesn't "replicate the essence" of the sieve. "Replicate" suggests it somehow follows the same process, which it certainly doesn't (it would be cleverer if it did). Neither does it describe anything that could reasonably be called the essence of the algorithm. It merely gives a vague idea of the process that's recognizable if you are familiar with the sieve. The description in the article sounds like unnecessary verbiage. 85.181.121.175 ( talk) 11:34, 28 April 2009 (UTC)
Euler in his Proof of the Euler product formula for the Riemann zeta function came up with a better version of the sieve of eratosthenes in which each number was eliminated exactly once.
This runs as follows. We start with the sequence of natural numbers
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35...
we then multiply each member of this sequence by two and remove from the original sequence to obtain
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35...
we then multiply each member of this sequence by three and remove from the working sequence to obtain
1 5 7 11 13 17 19 23 25 29 31 35...
we then multiply each member of this sequence by five (the first number after one) and remove from the working sequence to obtain
1 7 11 13 17 19 23 29 31 ...
Each member of the working sequence we remove is removed exactly once unlike the original Eratosthenes algorithm. If we continue with this process indefinately we will be left with just the number one in our working sequence, as in the Proof of the Euler product formula for the Riemann zeta function.
If however we store the eliminated prime numbers as they arrive in a queue and combine them with the working sequence when we have exceeded the square root of the upper limit of our range, we have the desired sequence of prime numbers. Of course we must also eliminate the remaining number one in our working sequence.
Zfishwiki ( talk) 00:08, 3 April 2009 (UTC)
This algorithm is I believe essentially equivalent to that described in Talk:Sieve_of_Eratosthenes#"A Reduced Redundant Exclusions (RRE) Prime Sieve", except that primes as they are discovered are now eliminated from the working sequence. However where that counted as new research, my algorithm is based on the Proof of the Euler product formula for the Riemann zeta function. I have therefore stuck as closely to Euler's algorithm as closely as possible
Please let me know whether this should be included in the original article. If so I think we should delete the reference to starting with the square of the working prime when eliminating further composite numbers, as although increasing the efficiency of the algorithm, it does not do so as efficiently as the algorithm here described does.
Zfishwiki ( talk) 00:08, 3 April 2009 (UTC)
Okay I have taken it upon myself to add this section to the article, in the absence of any discussion of it after seven days. My reason's for doing so are -:
Zfishwiki ( talk) 23:32, 9 April 2009 (UTC)
I disagree. I have described the algorithm in ordinary language which is easy to understand, rather than be excessively formal. I believe most people would understand that when I said we eliminate the prime numbers as they arrive and store them in in a queue, the number two would be included in this queue.
The first stage of the algorithm is to multiply the sequence by two (the first number after one to be explicit) and remove these numbers from the original sequence. I fail to see how this is any different from my treatment of the primes three and five. Common sense would indicate that it is to be treated in the same manner.
If I were to define my argument in a more exact fashion I believe this would reduce its readability and thus the value of the article.
Zfishwiki ( talk) 18:50, 24 June 2009 (UTC)
If you think you can explain the algorithm more simply, feel free to make the change. However I have taken a lot of care in my explanation and you might find it is harder than you think to improve it.
There is a good reason for including 1 in the working sequence. For example when we multiply by 3, this ensures that 3 is present in the multiplied sequence, and thus 3 is then eliminated from the working sequence. If 1 was not present in the working sequence, 3 would not be eliminated and we would have to complicate the algorithm by introducing some rule to eliminate 3. It is just more elegant mathematically to have the 1 constantly present.
I say towards the end of the algorithm that primes as they are eliminated are stored in a queue and this would include 2, most people know that 2 is a prime number, and 2 is therefore the first prime to be stored in a queue. I could explicitly say that each time we multiply the working sequence by a number, then that number is prime and is then stored in a queue. If it makes you happy go ahead and make that change.
Zfishwiki ( talk) 13:31, 25 June 2009 (UTC)
I have altered the final paragraph to explicitly say which numbers are to be stored in a queue, and how they are to be combined with the final working sequence. Hope this satisfies your concern.
Zfishwiki ( talk) 14:08, 25 June 2009 (UTC)
I have also labelled the primes as they arrive in the example, to avoid any possible confusion. In my opinion this makes the description of the algorithm more fussy, but that is just my opinion.
Zfishwiki ( talk) 14:29, 25 June 2009 (UTC)
A) Start with all the natural numbers except '1' that is not a prime. 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35... ^ B) The leftmost number is prime. Multiply each number in the list by this prime and discard the products. 2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35... ^ C) The number after the previous prime is also a prime. Multiply each number in the list starting from the latest prime by the latest prime and discard the products. 2 3 5 7 11 13 17 19 23 25 27 29 31 35... ^ Repeat C) indefinitely. On each repetition a new prime is identified (marked ^) until all the primes in the starting list have been found.
Cuddlyable3 ( talk) 20:40, 25 June 2009 (UTC)
Well this seems to be equivalent to my algorithm, although it does not stick as close to Euler's proof of the product identity, so could be construed as original research. Go ahead and make the change if it makes you happy.
Zfishwiki ( talk) 10:34, 26 June 2009 (UTC)
Done. Cuddlyable3 ( talk) 12:44, 26 June 2009 (UTC)
In Euler's proof we have a mathematical series on the right hand side, and we sift the series in waves until the right hand side consists solely of the term 1. We then rearrange the equation to get the product identity.
I have removed the statement that we are left with a sequence of primes in Euler's proof . If you want to explain how the algorithm relates to Euler's proof, I suggest you say that the primes to the left of the cursor correspond to factors on the left hand side of the equation at each stage, whereas the sequence to the right of the cursor corresponds to the series on the right hand of the equation.
Zfishwiki ( talk) 16:45, 26 June 2009 (UTC)
Okay I've made these changes.
Zfishwiki ( talk) 17:21, 26 June 2009 (UTC)
The article says that Euler's algorithm is better. It does not say why. It does not give the running time of Euler's algorithm, nor the storage requirement. There is also no specification of the algorithm in pseudo-code. I appreciate that an algorithm is mentioned here that is often not mentioned in discussions about the Sieve of Eratosthenes, but this section would be a lot more useful with the aforementioned information. - ATBS 15Aug09 —Preceding unsigned comment added by 71.112.25.123 ( talk) 11:13, 16 August 2009 (UTC)
I am not sure I agree with the present expansion of the explanation of Euler's algorithm. Whilst the former explanation was probably too concise, the present one is too unwieldly. There is no need to calculate all the multiples at each stage; we can stop when we have exceeded the upper range, and therefore we only need to print the preformatted multiple list up to the upper range in our description.
I won't make this change because I prefer the description given at the top of this section, which is closer to Euler's proof of his identity. I'll leave it to someone else to make the change if he wants to!
Zfishwiki ( talk) 00:45, 30 November 2009 (UTC)
From the description I get the idea that Euler's Sieve only remove's numbers that are the factor of 2 primes. For instance if I understood correctly then on the first run we remove the multiples of 2, then the multiples of 3 (which removes 9 because 3*3 = 9). Then we remove all the multiples of 5, 5*5 = 25, 5*7 = 35, 5*11 = 55 ... we have missed 45.
Please correct me if I'm wrong and remove the disputed notice I've attached. Thanks Genjix ( talk) 18:41, 22 June 2010 (UTC)
It's possible to view the positive integers as the vertices on a directed tree where the edges are multiplication by prime numbers. This implementation is typically slower than the sieve of eratosthenes, but it is very easy to adapt it to calculate phi and other functions : -- Nic Roets ( talk) 23:14, 11 May 2010 (UTC)
#define pmaks 1000000
int ppmaks/10], foundpmaks], i, j = 0;
void S (int k, int n)
{
int l;
foundn = 1;
for (l = 0; pl * n < pmaks && l <= k; l++) S (l, n * pl]);
}
int main ()
{
memset (found, 0, sizeof (found));
for (i = 2; i < pmaks; i++) {
if (!foundi]) {
pj = i;
S (j++, i);
printf ("%d\n", i);
}
}
}
I believe the algorithm shown in C is an implementation of Eratosthenes' sieve, not Euler's sieve. It visits each multiple of each prime found, not only the products of the prime with values still left in the list. However, it is listed under the section for Euler's sieve, which is misleading. -- 76.191.195.184 ( talk) 23:19, 26 December 2010 (UTC)