Prime number module

Andrew Dalke adalke at mindspring.com
Wed Oct 1 15:53:04 EDT 2003


Stephen Horne:
> I think bitsets are the way to go for compression. The idea of only
> storing every nth prime until you consider how you implement the seive
> for the missing primes.

Well, my idea was to store the counts for every, say, 10,000th prime
then do a fast prime test to fill in missing ranges, and cache that list
of primes for later use.

> Basically, you only need to store bits where (value % 6) is one of the
> values that gets a dot in the bottom line. Then to determine which bit
> you need, you set up something like...

You could also get better compression testing for %5, %7, %11, etc.
Note that by doing so you convert your lookup system into a simple
prime tester, and if you extend it along 2, 3, 5, ... then it is the seive
of Eratosthenes and you don't need to store any bit patterns at all.

                    Andrew
                    dalke at dalkescientific.com






More information about the Python-list mailing list