Prime number module

[Andrew Dalke]

Adding another thought to the discussion.  Instead of pregenerating
all primes using a seive, store the cumulative counts for, say,
every 10,000 terms (so 10,000 numbers are needed for the 1E8
range requested by the poster) then use a fast prime tester, like the
Rabin-Miller strong pseudoprime test (see
 http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html )
to fill in any missing range.  Could cache any hits in a bitstring
along with the counts, like

counts = [(None, 9999),  # however many are between 0 and 10000
               (None, 8888),  # between 10,000 and 20,000 (or 0 to 20,000)
                ...
              ]

where the None field stores the bitstring   May want to do every
1,000 if the tests are too slow.

pycrypto has Rabin-Miller and here's a copy I found in pure Python:
  http://senderek.de/pcp/release/tools/number.py

It uses the first 7 primes for tests, which is good for all numbers
up to 341550071728321 ~ 3.4E14.

                    Andrew
                    dalke at dalkescientific.com