Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Fast algorithm for finding number of p less than n

  1. Jun 11, 2006 #1
    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?
  2. jcsd
  3. Jun 11, 2006 #2
    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.

  4. Jun 11, 2006 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.

    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.
    Last edited: Jun 11, 2006
  5. Jun 11, 2006 #4
    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" :biggrin:
    Last edited: Jun 11, 2006
  6. Jun 14, 2006 #5
    hehe...I set myself the same damn problem last weekend :biggrin: ...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 gonna 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.)
    Last edited: Jun 14, 2006
  7. Jun 14, 2006 #6
    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 explaination of sieve :P
  8. Jun 14, 2006 #7


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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 sieve1 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.
    Last edited: Jun 14, 2006
  9. Jun 14, 2006 #8
    ouch! :redface: I stand corrected :smile:...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
    Last edited: Jun 14, 2006
  10. Jun 19, 2006 #9


    User Avatar
    Homework Helper

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

    Code (Text):

    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

       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

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

    Last edited: Jun 19, 2006
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook