# Fast algorithm for finding number of p less than n

1. Jun 11, 2006

### 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,

2. Jun 11, 2006

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

3. Jun 11, 2006

### Hurkyl

Staff Emeritus
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
4. Jun 11, 2006

### 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"

Last edited: Jun 11, 2006
5. Jun 14, 2006

### 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 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
6. Jun 14, 2006

### 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 explaination of sieve :P

7. Jun 14, 2006

### Hurkyl

Staff Emeritus
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
8. Jun 14, 2006

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

Last edited: Jun 14, 2006
9. Jun 19, 2006

### rcgldr

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

Last edited: Jun 19, 2006