On Fri, Nov 8, 2013 at 6:09 PM, Gregory Ewing <greg.ew...@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 -- https://mail.python.org/mailman/listinfo/python-list