Jump to content
  • Advertisement
Sign in to follow this  
Nice Coder

Generateing all primes from 2-N the fast way

This topic is 4913 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello all, i've been doing some primality generating recently: And i've been wondering, how many people have lists of all primes < 2^64? How long would it take to compute this list? (asuming one comp, 1ghz, with 256mb ram). How would you compute it efficiently? From, Nice coder

Share this post


Link to post
Share on other sites
Advertisement
I found a list of ways to test if numbers are prime @ Dr. Math, using some of the properties of primes it isn't hard to generate reasonbly fast tests.

A simple way to test if (an odd) n is prime is to do the following:


bool prime = true;
for(int a = 3 ; a < sqrt(n) && prime; a += 2)
{
if(n % a == 0)
{
prime = false;
}
}

Share this post


Link to post
Share on other sites
Quote:
Original post by Nice Coder
And i've been wondering, how many people have lists of all primes < 2^64?


I only have primes less than 10.006.721 - in a handbook.

Quote:
How long would it take to compute this list? (asuming one comp, 1ghz, with 256mb ram).


Depends on the algorithm you use.

Quote:
How would you compute it efficiently?


Primality testing @ Mathworld.

Share this post


Link to post
Share on other sites
Quote:
Original post by Nice Coder
Hello all, i've been doing some primality generating recently:

And i've been wondering, how many people have lists of all primes < 2^64?

How long would it take to compute this list? (asuming one comp, 1ghz, with 256mb ram).

How would you compute it efficiently?

From,
Nice coder

If you are working in C++ and you are worried about cost of calculation during the runtime of your program, you can compute the list at compile-time with the algorithm of your choice by using template (or even preprocessor) metaprogramming. This way, it would have literally no runtime cost in terms of calculation regardless of the method you use (though you'd still want a fast one otherwise your compile time will go through the roof). Also because of this, you get the added benefit of being able to use the list at compile-time if you would happen to need it.

Share this post


Link to post
Share on other sites
libgmp has a nextprime() function, which might suit your needs well. [it actually doesn't -guarantee- that the numbers are prime, but gives ~7 9's worth of likelihood]

Though, 2^64 is fairly large, so sieving through the entirety of the range should prove impractical.

There was a recent breakthrough in India [?] regarding primality testing, which might help.

Share this post


Link to post
Share on other sites
Quote:
Original post by Telastyn
libgmp has a nextprime() function, which might suit your needs well. [it actually doesn't -guarantee- that the numbers are prime, but gives ~7 9's worth of likelihood]

Though, 2^64 is fairly large, so sieving through the entirety of the range should prove impractical.

There was a recent breakthrough in India [?] regarding primality testing, which might help.


Sieving up to 2^32 is also impractical.

I've got lists to about a billion, but it took a few hours to get them (a version of trial division, using vb.)

From,
Nice coder

Share this post


Link to post
Share on other sites
Isn't there a formula, like 6x +-1 or something, which dictates most of the primes?

What is that formula?

From,
Nice coder

Share this post


Link to post
Share on other sites
Sieving up to 2^32 is impractical, but possible for some. With 768 MB DDR RAM, and only about 26 used by OS and background software, I easily have room for 256 2-MB unpaged chunks. All those together gives 512 MB. Which is 2^32 bits exactly. I've used this technique a couple times before, primarily for testing 32-bit digest algorithms.

Using trial division, my old 266MHz Pentium-1 laptop could spit to human-readable text file all the primes up to ~200,000,000 in eight hours, but could get the first 20,000,000 in only about three minutes.

Share this post


Link to post
Share on other sites
How would the code go with that? (one bit per number).
(please bear in mind that i'm working in vb, where mod only goes up to 2^16, and everything is really really slow).

I've only got 256mb of ram, so i can't do that :(.

Ow well, i'll go up to maybe 2B-3B then i'll trial divise the rest.

From,
Nice coder

Share this post


Link to post
Share on other sites
Quote:
Original post by Wyrframe
Sieving up to 2^32 is impractical, but possible for some. With 768 MB DDR RAM, and only about 26 used by OS and background software, I easily have room for 256 2-MB unpaged chunks. All those together gives 512 MB. Which is 2^32 bits exactly. I've used this technique a couple times before, primarily for testing 32-bit digest algorithms.

Using trial division, my old 266MHz Pentium-1 laptop could spit to human-readable text file all the primes up to ~200,000,000 in eight hours, but could get the first 20,000,000 in only about three minutes.


Mines 48 secs to 100K. (thats just a prototype).
edit: 5 secs at 100K
107Sec to 1M

How fast is yours?
From,
Nice coder

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!