Primec Format

Previous

The primec format exploits the fact that all primes greater than 5 end in the decimal digits 1, 3, 7, or 9. Thus, the primality of 20 successive numbers can be specified in one 8 bit byte. The file begins with the complete binary representation of:

The beginning of the sequence
The end of the sequence
A check sum of all data bytes
(All three are 8 bytes for this implementation).

The first and last values are a multiple of twenty, thus are never primes. There is no overlap of primes between successive files that use the same number for the upper boundary of the first file, and the lower boundary of the second file.

The primality of any number in the range of the file is determined as follows:

If the number ends in 0, 2, 4, 5, 6, or 8, it is not prime.
Otherwise, the location of the specifying byte is at offset:
( value - start ) / 20
Within that byte, the primality of the value is specified by the bit as shown in the following table.

The only tedious programming tasks were:

Special case code for values less than 20, which include 2 and 5, and exclude 1 and 9. All larger values follow the same simple pattern.
The increment and decrement operators for the corresponding iterators must search forward (or backward) for the next true bit, specifying the next prime number.

This table shows the layout and content for a file containing 20 to 60. The first 24 bytes (start value, end value, check sum) are not shown.

Byte 0 1
Bit 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
Value 21 23 27 29 31 33 37 39 41 43 47 49 51 53 57 59
Prime F T F T T F T F T T T F F T F T
Hex 5A E5

As primes become larger, the density of primes becomes smaller as 1/ln(n). Thus the density of true bits also falls off. The number of digits (binary or decimal) to represent the primes grows as ln(n). Thus, a sequence of primes represented as primec is always competitive in size with the corresponding sequence in ASCI text or binary, besides providing fast direct access by value:

bool isPrime(value).

The results for the sequence of the largest 64 bit primes (18446744073707000000 to 18446744073709551558) is:

Format Size
(KB)
64 Bit Binary 445
Txt 1150
Zip Txt 114
PrimeC 125


                                                                                                                                                                                                                                                                                                           

Clyx.com


Top of Page
Top of Page