Fast algorithm for finding number of p less than n

[heartless]

Hello,
I'm looking for some good and fast algorithm to find all prime numbers less than a given number. I've got a simple program which finds all primes less than any number, but once n gets above 500,000 it takes much too long. (More than 5 minutes. Just up to 100000 it takes about 7 seconds.)
My method is simply sieve of Eratosthenes, divide each number by every consecutive and so on. What'd be your method?
Thanks,

 

[Rach3]

There are very fast primality tests. Start with wikipedia's page to see the general picture, then you can follow the links to descriptions of the algorithms, or [much easier] working implementations.

http://en.wikipedia.org/wiki/Primality_test

 

[Hurkyl]

My method is simply sieve of Eratosthenes, divide each number by every consecutive and so on.

That's not the right way to do the sieve!

You shouldn't sieve by every number... only the primes! Remember how you did it by hand: you started off by crossing off every multiple of 2, then you saw 3 was prime, and crossed off every multiple of 3.

Did you then cross off every multiple of 4? No! You went straight to 5, because that's the next prime!



There are better sieves, but more complicated, and this one should be more than enough for your purposes.

There are very fast primality tests.

That's not the way you want to do it; primality testing is only good if you have a few numbers you want to test. Sieving is better, because it works on all the numbers simultaneously.

 

[MemoryOfUs]

The newest method I just knew -well, maybe a little out-of-date to most of you- is to use Pythagore

]edit[ it's "gore" not "gon"

 

[GregA]

hehe...I set myself the same damn problem last weekend ...for me things get slow at 20,000 but my algorithm so far is the ultimate in basic...what I am trying so far though is to get some code to work properly where it only checks for divisibility by numbers less than sqrt(n) (if a number p higher than n's square root divides n then the result would have been a number less than p that divides n anyway..so continuing is pointless)...damn thing isn't working yet though :grumpy: ...once I've done this I'm going to figure out how to make it start at n = 1, check every n and throws whatever primes it finds into an array and only uses these to divide all subsequent n...ie; the sieve (I know vaguely what I have to do but I don't quite have the knack yet of making my computer do as its told without acting silly.)

 

[heartless]

That's probably because you're using delphi or pascal, dunno.
Thanks guys for help, I'll code using the given algorithm.
Hurkyl, that was a shortened explanation of sieve :P

 

[Hurkyl]

check every n and throws whatever primes it finds into an array and only uses these to divide all subsequent n...ie; the sieve

If I understand you correctly, that's not a sieve. In fact, that's the very thing a sieve is designed to avoid! If you're doing a sieve¹ to find all the primes less than some bound, you will never do any divisions at all!

The whole point of a sieve is that you are not doing a bunch of work for one number, then a bunch of work for the next number, and so forth... but instead are working with the entire collection of numbers at once.

Wikipedia has a nice animation of how the sieve of Eratosthenes works.



1: at least, if you're doing the simplest sort of sieve. More complicated sieves might require some divisions for the setup, but not for the actual sieving.

 

[GregA]

ouch! I stand corrected ...not that it will do me any good but what I meant was say we're lookiing at n = 5, then using p=2 and the fact that the next prime stored... 3 is greater than sqrt(5) store 5 as a prime then look at 6, and dis-regard it, look at 7 and again only use 2 and store it as a prime...disregard 8,9,10, use only 2 and 3 to divide 11 before storing it as a prime and so on... pulling all multiples of the primes (up to a certain number) out of a* look at these numbers* box is something I will give more thought

 

[rcgldr]

I didn't see any full explanations of the sieve method.

Start off with an array of n bytes
Set all bytes to a 1.

Set the prime index to 2.

while ((prime index squared) < n)
   Set the array index to the prime index squared.
   While(array index < n)
      clear byte at array index
      add prime index to array index
   endwhile

   starting at prime index +1, scan for next byte in array == 1
   (note Intel / AMD processors have an assembly instruction,
    repne scasb (AL==1), that can speed this up greatly,
    else do this via a loop).
   set new prime index to the index of the next byte == 1
endwhile

Rescan array from 2 to n-1, the indexes of all bytes == 1 are primes.