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.

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

Hmm...

Maybe you're right...

It worked for mine though ... or did it...

::goes and checks::

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

I actually remember doing this quite young at school, although our "array" was defined on squared paper

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

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!

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.

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