listing 15-digit primes

[fivemack]

What's the current state of the art in software for listing the primes in medium-sized intervals a reasonable way along the number line (say 10^14-10^9 .. 10^14) on a CPU?

Also, if I've gone to the bother of writing a very fast CUDA routine for listing large primes, are there any interesting number-theoretical things to _do_ with the large primes? I suppose a wise person would have asked this before writing the routine, but never have I called myself a wise person.

(would it be interesting to try to write some CUDA code for sieving Sierpinski numbers or similar?)

[R.D. Silverman]

Originally Posted by fivemack

What's the current state of the art in software for listing the primes in medium-sized intervals a reasonable way along the number line (say 10^14-10^9 .. 10^14) on a CPU?

What do you mean by "list"? Store on disk? Is compactness of the
representation important? (e.g. one can 'list' all the primes in an interval
of length 10 using just 4 bits).

Finding the primes in such an interval is best done by a simple Sieve
or Eratosthenes.

Also, if I've gone to the bother of writing a very fast CUDA routine for listing large primes, are there any interesting number-theoretical things to _do_ with the large primes?

-- Construct pseudo RNGs. Whether this is 'interesting' depends upon
one's viewpoint.

-- Help out in Goldbach computations.

There really are not many uses for lists of large primes.

[R.D. Silverman]

Originally Posted by R.D. Silverman

What do you mean by "list"? Store on disk? Is compactness of the
representation important? (e.g. one can 'list' all the primes in an interval
of length 10 using just 4 bits).

Finding the primes in such an interval is best done by a simple Sieve
or Eratosthenes.



-- Construct pseudo RNGs. Whether this is 'interesting' depends upon
one's viewpoint.

-- Help out in Goldbach computations.

There really are not many uses for lists of large primes.

Note that implementing Brent's sub-linear sieve might be
useful, but it depends on the size of the primes and the length of the
interval. There is a fair amount of pre-computation overhead.

[fivemack]

Originally Posted by R.D. Silverman

What do you mean by "list"? Store on disk? Is compactness of the
representation important? (e.g. one can 'list' all the primes in an interval
of length 10 using just 4 bits).

Finding the primes in such an interval is best done by a simple Sieve
of Eratosthenes.

With respect, I would say that finding the primes in such an interval is (probably) best done by a sophisticated implementation of the sieve of Eratosthenes; the question of when to move from checking each entry in the array for divisibility by small primes, by techniques similar to texture mapping, to randomly writing to the array in the positions corresponding to the large primes, perhaps with bucketting techniques, gets less trivial the more I work on it.

The Goldbach testing is up to 1.5e18, which needs about a 64MB array to store the small primes (one byte per difference) ...

[garo]

You may want to look at this page for ideas:

http://www.troubleshooters.com/codec...imenumbers.htm

[R.D. Silverman]

Originally Posted by fivemack

With respect, I would say that finding the primes in such an interval is (probably) best done by a sophisticated implementation of the sieve of Eratosthenes; the question of when to move from checking each entry in the array for divisibility by small primes, by techniques similar to texture mapping, to randomly writing to the array in the positions corresponding to the large primes, perhaps with bucketting techniques, gets less trivial the more I work on it.

The Goldbach testing is up to 1.5e18, which needs about a 64MB array to store the small primes (one byte per difference) ...

I meant that the *algorithm* is simple. Of course one can (and should) do
a sophisticated implementation. I separate the two.

BTW, one stores HALF the distance, not the distance itself, since it is
always even.

[Mini-Geek]

Originally Posted by R.D. Silverman

I meant that the *algorithm* is simple. Of course one can (and should) do
a sophisticated implementation. I separate the two.

BTW, one stores HALF the distance, not the distance itself, since it is
always even.

What do you do when the gap is above 512 (which is double the amount you can store in one byte)? The first such occurrence is after a 12-digit prime (304599508537), so this won't really cause any problems until you're searching around 24 digits...so I guess anything only storing one byte per diff just has that limit.

[R.D. Silverman]

Originally Posted by Mini-Geek

so I guess anything only storing one byte per diff just has that limit.

Yep.

[CRGreathouse]

I suppose once you run out of space you just move to two bytes. That shouldn't be exhausted until > 10^157 if you believe Cramér.