Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 what is the fastest way of generating primes
Index -> Programming, C++ -> C++ Help
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
liangchenen




PostPosted: 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.
Sponsor
Sponsor
Sponsor
sponsor
wtd




PostPosted: Thu Jun 09, 2005 8:24 pm   Post subject: (No 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.
md




PostPosted: Fri Jun 10, 2005 12:59 am   Post subject: (No 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.
wtd




PostPosted: Fri Jun 10, 2005 1:22 am   Post subject: (No 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.
md




PostPosted: Fri Jun 10, 2005 11:18 am   Post subject: (No 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.
Martin




PostPosted: Fri Jun 10, 2005 1:48 pm   Post subject: (No 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.
Display posts from previous:   
   Index -> Programming, C++ -> C++ Help
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 6 Posts ]
Jump to:   


Style:  
Search: