Generateing all primes from 2-N the fast way
Author
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
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:
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; }}
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.
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.
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.
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.
Author
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
Author
Isn't there a formula, like 6x +-1 or something, which dictates most of the primes?
What is that formula?
From,
Nice coder
What is that formula?
From,
Nice coder
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.
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.
Author
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
(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
Author
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
