Computer Science Canada

what is the fastest way of generating primes
Author:  liangchenen [ Thu Jun 09, 2005 7:49 pm ]
Post subject:  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.
Author:  wtd [ Thu Jun 09, 2005 8:24 pm ]
Post subject: 
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.
Author:  md [ Fri Jun 10, 2005 12:59 am ]
Post subject: 
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.
Author:  wtd [ Fri Jun 10, 2005 1:22 am ]
Post subject: 
Cornflake wrote:
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.
Author:  md [ Fri Jun 10, 2005 11:18 am ]
Post subject: 
wtd wrote:
Cornflake wrote:
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 Wink It's a great method for finding primes in a given list; but there are better ways of finding primes.
Author:  Martin [ Fri Jun 10, 2005 1:48 pm ]
Post subject: 
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.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy