20050316, 20:44  #12 
Jan 2005
Transdniestr
767_{8} Posts 
Doh, I found much better (and pretty obvious) way to store them:
http://www.rsok.com/~jrm/printprimes.html 
20050317, 23:29  #13  
6,947 Posts 
Quote:
The one subtlety that arises here is: what to do with a gap of precisely length 512? (Length 2^(n+1) for the general nbitfield 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 zerovalued bytes (each of which denotes a length512 interval), i.e. the byte pair 00000000 11111111 represents a 512gap, the byte triplet 00000000 00000000 11111111 represents a 1024gap, 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 1bit 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). 

20050318, 10:17  #14  
3^{2}×5×167 Posts 
Quote:
If your aim is to store primes as compactly as possible, the 4bit 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 230, which would each require half a byte. I've assumed a simple scheme where the next half byte codes gaps 3260, the third half byte 6290 etc. This scheme needs about 25200 bytes to store the range or about 77% of the fullbyte scheme. 

20050318, 14:04  #15  
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
5×2,179 Posts 
Quote:
Last fiddled with by Uncwilly on 20050318 at 14:04 

20050318, 17:42  #16  
10001011111100_{2} Posts 
Quote:
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 

20050318, 19:55  #17 
Jan 2005
Transdniestr
111110111_{2} Posts 
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 17 3 bits  sieve gaps 17 8 bits  sieve gaps 823 12 bits  sieve gaps 24128 16 bits  sieve 1291024 (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 30030sieved 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. 
20050319, 00:18  #18 
Mar 2005
2×5×17 Posts 
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. 
20050320, 00:50  #19 
Jan 2005
Transdniestr
111110111_{2} Posts 
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 quickanddirty 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 230, 8 for 3262, 12 for 6494 (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.11.2*10^12. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Here is a list of Mersenne Primes  MattcAnderson  MattcAnderson  0  20170527 14:00 
List of megabit primes found  Lennart  Twin Prime Search  58  20170505 14:15 
List of all base 5 primes?  gd_barnes  Sierpinski/Riesel Base 5  2  20080701 04:09 
Mistake in List of Primes  rogue  Sierpinski/Riesel Base 5  1  20070223 00:35 
Does Prime95 has a list of primes inside it???  hyh1048576  Software  5  20030820 13:38 