| x404.co.uk http://www.x404.co.uk/forum/ |
|
| Sieve of Eratosthenes http://www.x404.co.uk/forum/viewtopic.php?f=4&t=14503 |
Page 1 of 1 |
| Author: | Fogmeister [ Fri Aug 19, 2011 10:28 am ] |
| Post subject: | Sieve of Eratosthenes |
WOW! I love this thing! Just learnt about it the other day after JonLumb mentiong it. Had a look at it and it's amazing! Anything using prime numbers now and I can pull this thing out of my toolbox. Sooooooo quick even working out primes upto 1,000,000 takes a fraction of a second. The iteration steps go something like this... 1. Create an array of n boolean values and set them all to true (where n is the maximum number you want to test upto). 2. Set p = 2. 3. Start at p and then set all multiples of p (i.e. 2p, 3p, 4p...) in the array to false until you get to the end of the array. 4. Now step through the array until you get to a value of p in the array of true. 5. Repeat step 3 and 4 until your value of p reaches the limit of the array. Now you can read through the array and any value in the array that is true is a prime number. Genius! And very quick! Not sure what order it is but it is definitely below O(n). ::Corrected:: This can be made more efficient by starting step 3 at p^2 as all previous multiples of p will have been marked already. Further, you can imporve it more by stopping when p > sqrt(n) as the largest prime factor of n is <= sqrt(n). This allows the squaring rule above as without it it is possible for p^2 to be too large. |
|
| Author: | jonlumb [ Fri Aug 19, 2011 11:33 am ] |
| Post subject: | Re: Sieve of Eratosthenes |
Not following that last line Oli, the way I read it you start off testing p=2, then test p=3 (2^2 -1) and then you end up with p=8 (3^2 -1), which misses out 5 and 7... |
|
| Author: | Fogmeister [ Fri Aug 19, 2011 12:13 pm ] | |||||||||
| Post subject: | Re: Sieve of Eratosthenes | |||||||||
Hmm... Maybe you're right... It worked for mine though ... or did it... ::goes and checks:: |
||||||||||
| Author: | Fogmeister [ Fri Aug 19, 2011 12:18 pm ] |
| Post subject: | Re: Sieve of Eratosthenes |
Ah, I read it wrong. I wasn't actually using it yet just doing the ++ method. The actually thing is to start marking false from p^2 rather than 2p, 3p, etc... |
|
| Author: | JJW009 [ Fri Aug 19, 2011 12:41 pm ] |
| Post subject: | Re: Sieve of Eratosthenes |
I actually remember doing this quite young at school, although our "array" was defined on squared paper 
|
|
| Author: | Fogmeister [ Fri Aug 19, 2011 12:47 pm ] | |||||||||
| Post subject: | Re: Sieve of Eratosthenes | |||||||||
There's a number of the Project Euler problems that I have done with pencil and paper or just using simple formalae in Excel. I wouldn't like to do this up to 1,000,000  which currently takes my PC about 0.2 seconds (and I'm about to make it quicker).OK, you can also stop checking when p > sqrt(n). |
||||||||||
| Author: | JJW009 [ Fri Aug 19, 2011 1:17 pm ] | |||||||||
| Post subject: | Re: Sieve of Eratosthenes | |||||||||
Spare a thought for the people who did exactly this. All those log tables people used until not so long ago were all calculated by hand too! |
||||||||||
| Author: | jonlumb [ Fri Aug 19, 2011 2:29 pm ] | |||||||||
| Post subject: | Re: Sieve of Eratosthenes | |||||||||
That's only for telling if there are prime factors; if you want them all you need to keep going (or use an additional process). You can however stop when p > n/lowest prime factor. |
||||||||||
| Author: | Fogmeister [ Fri Aug 19, 2011 3:01 pm ] | ||||||||||||||||||
| Post subject: | Re: Sieve of Eratosthenes | ||||||||||||||||||
When you start checking P you know for a fact that (P-1)P, (P-2)P, ... 2P have already been checked as they will all have been multiples of numbers less than P. i.e. if P is 9 then you know already that 18 (i.e. 2P) is a multiple of 2 and so will have been checked already. So, the first multiple of P you need to check is P^2 (i.e. P * P). If for example n = 100 and your current P value is 11 then you only need to start checking multiples of P >= 121 which is already over n so doesn't need checking anyway. For primes up to the value of n it is sufficient to only check multiples of P up to and including sqrt(n). |
|||||||||||||||||||
| Page 1 of 1 | All times are UTC |
| Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |
|
