Algorithm that makes maximum compression of completly diffused data.

Chris Angelico rosuav at gmail.com
Fri Nov 8 08:21:59 CET 2013


On Fri, Nov 8, 2013 at 6:09 PM, Gregory Ewing
<greg.ewing at canterbury.ac.nz> wrote:
> You've got me thinking now about how viable a compression
> scheme this would be, efficiency issues aside. I suppose
> it would depend on things like the average density of primes
> and the average number of prime factors a number has.
> Any number theorists here?

Start by coming up with an efficient storage representation for the
primes. Don't forget that you can't use a bitfield, because eg 98 =
7*7*2, so you somehow need to represent that the 7 comes up twice. And
you can't limit the size of your primes (eg by representing 98 as
"\x07\x07\x02").

And that's without dealing with the major issue of _finding_ prime
factors for a large number.

ChrisA



More information about the Python-list mailing list