pack_primes.py

# https://stackoverflow.com/a/568618
def gen_primes():
    D = {}
    q = 2
    while True:
        if q not in D:
            yield q
            D[q * q] = [q]
        else:
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]
        q += 1


filesize = 30 * 1024
base_arr = bytearray()
diff_arr = bytearray()
block_sz = 29


def pack():
    n = 0
    for p in gen_primes():
        if p == 2: continue
        if n % block_sz == 0:
            base = p
            base_arr.append(p & 0xFF)
            base_arr.append((p >> 8) & 0xFF)
            base_arr.append((p >> 16) & 0xFF)
        else:
            diff_arr.append((p - base)//2)
        n += 1

        if len(base_arr) + len(diff_arr) >= filesize:
            # remember the last prime for testing
            global last_p
            last_p = p
            break


def fetch_nth_prime(n):
    # special case for 2
    if n == 0:
        return 2

    n -= 1

    # fetch base
    i = n // block_sz
    p = base_arr[3*i] | (base_arr[3*i+1] << 8) | (base_arr[3*i+2] << 16)

    j = n % block_sz
    if j > 0:
        # add difference
        p += 2 * diff_arr[(block_sz-1)*i + j-1]

    return p


def test():
    for n, p in enumerate(gen_primes()):
        if p > last_p: break
        #print(p, fetch_nth_prime(n))
        assert p == fetch_nth_prime(n)


pack()
test()