Prime number module

[Lulu of the Lotus-Eaters]

bokr at oz.net (Bengt Richter) wrote previously:
|just make a bit map of the 10**8 on disk, which would only be
| >>> 10**8/8000000.
| 12.5
|megabytes.

I had been thinking about this also, but Bengt beat me to posting
something.  I think that we could pick up Emile van Sebille's suggestion
about gaps only needing to store even numbers here; the equivalent being
that we only store a bit array of ODD numbers, getting us down to 6.25
mB of storage space (special casing of the prime '2' needs to be
handled, seems manageable :-)).

Doing this does not necessarily produce a smaller storage format than a
zip'd bitmap of all the numbers.  But the in-memory image doesn't
require a decompression step (and the stored version can still be
compressed).  I guess the test is something like:

    prime_bits = open('bitarray.primes','rb').read() # only odd nums
    def isPrime(N):
        if N < 2:  return False
        elif N==2: return True
        else:
            byte, bit = divmod(N, 16)
            bit = bit//2
            return ord(prime_bits[byte]) & 2**bit

You could also use a memory-mapped file or the like, of course.

|Nth-prime and how-many-below-N would need some other representations.
|You could translate the bit map to a sequence of prime counts for 8 or 16-bit
|chunks with a simple 2*8 or 2**16 byte table mapping bytes or 16-bit chunks to
|the counts of bits within them, then sum and only fiddle with one bit chunk to
|make an nth-prime table...

The ancillary data structure would indeed speed the "how-many-below"
calculation enormously, while not taking too much space.

Along those lines, what's the quickest way to count bits in Python?
Maybe someone has a clever idea... something that would run a whole
bunch faster than my bit mask style above for counting all the "1"s in a
multibyte string.

Yours, Lulu...

--
 mertz@   _/_/_/_/_/_/_/ THIS MESSAGE WAS BROUGHT TO YOU BY:_/_/_/_/ v i
gnosis  _/_/                    Postmodern Enterprises         _/_/  s r
.cx    _/_/  MAKERS OF CHAOS....                              _/_/   i u
      _/_/_/_/_/ LOOK FOR IT IN A NEIGHBORHOOD NEAR YOU_/_/_/_/_/    g s