List of primes

[grandpascorpion]

Doh, I found much better (and pretty obvious) way to store them:

http://www.rsok.com/~jrm/printprimes.html

Originally Posted by ewmayer

Regarding the storage issue, there's no need to store the primes explicitly - you simply store a table of differences between consecutive primes.

...

...nearly all the prime gaps will be smallish (say less than 512), so a byte suffices to store any gap that is < 512 in gap/2 form. What do we do if a gap is larger? Well, since we know a gap must be > 0, we can reserve a zero-valued byte as a representing 512-plus-whatever-the-bext-byte-times-2-is. We can have as many zeros in a row as needed, i.e. can cover gaps of arbitrary size this way. Since gaps this large are very rare, that only trivially increases our storage.

Addendum #2:

The one subtlety that arises here is: what to do with a gap of precisely length 512? (Length 2^(n+1) for the general n-bit-field scheme.) Without modification, that would lead to an infinite string of zero bytes. To handle that, we only allow each nonzero byte to represent gaps from length 2 (byte = 00000001 in binary) to 510 (11111110), and use 11111111 to represent a *zero* terminating a string of zero-valued bytes (each of which denotes a length-512 interval), i.e. the byte pair 00000000 11111111 represents a 512-gap, the byte triplet 00000000 00000000 11111111 represents a 1024-gap, and so forth. It's still very simple to implement in code, and has one additional nice property which I neglected to mention in my initial post: in the lower limit of a 1-bit field length (n = 1), the resulting bit table is exactly the same one that results from simply labeling all the odd integers in the interval in question with a 0 (not prime) or 1 (prime).

Originally Posted by grandpascorpion

Since 6 is still the "jumping champion" in this range, I think you could save even more space by using a 4-bit solution.


...I could be wrong here. I haven't crunched any numbers but on the surface, it looks like most of the time you would use half the space.

If your aim is to store primes as compactly as possible, the 4-bit solution wins for this size range. I've looked at the range (2*10^13, 2*10^13+10^6) which yields 32,764 primes, with a maximal gap of 376. About 65% of the gaps are 2-30, which would each require half a byte.


I've assumed a simple scheme where the next half byte codes gaps 32-60, the third half byte 62-90 etc. This scheme needs about 25200 bytes to store the range or about 77% of the full-byte scheme.

[Uncwilly]

Originally Posted by Unregistered

I've assumed a simple scheme where the next half byte codes gaps 32-60, the third half byte 62-90 etc. This scheme needs about 25200 bytes to store the range or about 77% of the full-byte scheme.

Is it possible to post some of the code that you used?

Originally Posted by Uncwilly

Is it possible to post some of the code that you used?

I didn't use any code: I generated the primes using dsouza123's program, copied them into excel and counted the frequencies.

They were
2 to 30 21202
32 to 60 7604
62 to 90 2635
92 to 120 907
122 to 150 273
152 to 180 95

152+ 48

total: 32764

so 21202 gaps will code in 4 bits, 7604 in 8 and so on

[grandpascorpion]

Unregistered,

I think there's an even better way to do this, albeit a tad harder to implement.

Start with a set of numbers relatively prime to some product of the first n primes, like 30030 or 510510. That set will always be the primes to that point minus the prime factors plus 1. The sieved set size for 30030 is 3243.
So, 1 in sieve gap terms translates roughly on average to 9.

Since you dealing with a sieved range, it stands to reason that these sort of gaps would be much smaller. I would imagine a 3 bit would be implementable
for gaps 1-7

3 bits - sieve gaps 1-7
8 bits - sieve gaps 8-23
12 bits - sieve gaps 24-128
16 bits - sieve 129-1024 (rarely necessary)

I did a check: the minimum gap check for 23 for a sieved set of 30030 is 96. So, all gaps under <=96 could be handled in 8 bits.
Similarly, for 3 bits, all gaps under 7 (a real gap of 26) could be handled.

Note: These are min. values, the max values for the 30030-sieved gaps of 7 and 23 are 130 and 318 respectively.

I'll try to implement this this weekend and see how compact it would be.

[Richard Cameron]

Grandpascorpion


I think your approach could reduce the storage requirement quite a bit. But it all depends on the distribution of gaps, not just the average sizes. So I'm interested to see what results you get.


Richard Cameron

-thought it would be polite to register.

[grandpascorpion]

Hi Richard,

I got off on the wrong foot with the sieved range. I was working with the primes themselves not the set of relatively prime numbers.

I worked with 30030 sieve (2*3*5*7*11*13).

I ran a very similar range (a little bit different due a quick-and-dirty sieve implementation)

There were 33424 primes from 19999999999980 to 20000001020999
Max sieve gap is: 72 and max real gap is 376
444 Bit Total: 143212, 353 Bit total: 146644, Avg. is 4
Sieveless Bit Count: 203204

The sieveless count is 4 bits for 2-30, 8 for 32-62, 12 for 64-94 (so this would be take a bit less space than your scheme)

As you can see, it takes lroughly 16kb to store the primes within roughly a 1Mb range. Not using a sieve, takes more than 25k.

It may be overkill but I'll try the next higher range 510510 (30030*17) and see how much that would improve the storage.

BTW, for the 30030, sieve range the 353 scheme (3 bits < 8, 8 bits < 24, 11 bits < 64) does better through about 1.1-1.2*10^12.