Prime number module

[Tim Hochberg]

Alex Martelli wrote:
> Tim Hochberg wrote:
>    ...
> 
>>I believe you could implement a hybrid scheme that would be quite fast
>>and still maintain nearly the same level of compression that you
>>describe above. In addition to the above compressed data, also store,
>>uncompressed, every Nth prime. A binary search will get you within N
>>primes of your answer, to find the exact value, recreate those N-primes.
>>For a N of, for instance, 64 the level of compression would be minimally
>>affected but should make finding the number of primes less than a given
>>number number much faster than the basic compressed scheme.
> 
> 
> Still thinking of gmpy's primitives, I came up with a variant of this...:
> 

[Nice compact version using gmpy snipped]

Just to keep my hand in, I'm attaching a version based on the idea above 
which is in turn based on Emile's and Lulu's ideas for compression.

This produces data files that total just over 6 GB for all primes up to 
1E8. The initial run is quite slow, but after that it can determine the 
nth prime, or the number of primes below some number in about 0.5 ms on 
my box.

> The first run, building the file primes.dat (just 23048 bytes), took
> almost 7 minutes elapsed time on my machine (250 CPU seconds).  But
> any successive run is extremely fast:
> 
> [alex at lancelot perex]$ time python -O prio.py
> 5762 primes stored (1 every 1000), highest is 99991609
> 55555th prime is 686671
> Up to 555555, there are 45741 primes
> 0.06user 0.00system 0:00.14elapsed 41%CPU (0avgtext+0avgdata 0maxresident)k
> 0inputs+0outputs (494major+297minor)pagefaults 0swaps
> [alex at lancelot perex]$
> 
> I've coded this rapidly and sloppily, so I wouldn't be surprised if
> there were off-by-one errors here and there (needs to be checked against
> some other, independent way to generate/check primes!), but I think the
> fundamental ideas are sound.

Well one of us is off by one as I get 45740 primes below 55555. However, 
I get 686671 as the 55555th prime, so we agree there. I would not be at 
all suprised if it is mine that is off by one.

-tim

> 
> Alex
> 

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: packedprimes.py
URL: <http://mail.python.org/pipermail/python-list/attachments/20030930/2cb96dea/attachment.ksh>