# Generateing all primes from 2-N the fast way

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

## 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 on other sites
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 on other sites
Quote:
 Original post by Nice CoderAnd 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 on other sites
Quote:
 Original post by Nice CoderHello 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 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 on other sites
Quote:
 Original post by Telastynlibgmp 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 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 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 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 on other sites
Quote:
 Original post by WyrframeSieving 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

• 16
• 9
• 13
• 41
• 15