-----------------------------------

liangchenen

Thu Jun 09, 2005 7:49 pm


what is the fastest way of generating primes

-----------------------------------

if I have an array size 100,000,000 of bool  name prime
so, if 2 is prime

prime[2]=true;

4 if not a prime
prime[4]=false;

so, what is the fastest way of generating all the primes under 100,000,000.


-----------------------------------

wtd

Thu Jun 09, 2005 8:24 pm



-----------------------------------

Whatever you do, don't statically allocate that array.

As well, using an array of unsigned ints and bit shifting might prove more memory efficient.


-----------------------------------

md

Fri Jun 10, 2005 12:59 am



-----------------------------------

one way would be to go from the lowest number to the highest and if hte number is prime set all the multiples of that number to false.

so starting at 2, you'd set 4, 6, 8, 10, etc to false as they are multiples of 2. Next you do three. Since 4 is false it isn't prime and you skip it. Repeat until you've come to hte end of your array.


-----------------------------------

wtd

Fri Jun 10, 2005 1:22 am



-----------------------------------

one way would be to go from the lowest number to the highest and if hte number is prime set all the multiples of that number to false.

so starting at 2, you'd set 4, 6, 8, 10, etc to false as they are multiples of 2. Next you do three. Since 4 is false it isn't prime and you skip it. Repeat until you've come to hte end of your array.

Erastosthenes would like this idea.


-----------------------------------

md

Fri Jun 10, 2005 11:18 am



-----------------------------------

one way would be to go from the lowest number to the highest and if hte number is prime set all the multiples of that number to false.

so starting at 2, you'd set 4, 6, 8, 10, etc to false as they are multiples of 2. Next you do three. Since 4 is false it isn't prime and you skip it. Repeat until you've come to hte end of your array.

Erastosthenes would like this idea.

Perhaps becuse I stole it from him ;) It's a great method for finding primes in a given list; but there are better ways of finding primes.


-----------------------------------

Martin

Fri Jun 10, 2005 1:48 pm



-----------------------------------

Fastest way to generate primes is to make a list of all of the primes that you could possibly need in a file and then just use those.