[John_KZ]

Yep. A prime-based compression algorithm is possible, but if you don't store the whole number, it will take forever to calculate. How are you going to describe it? Are you going to say it's the Nth prime, so go ahead and calculate all (N-1) primes to find it? That's a lot of primes. And by that point it's not any different than sharing data with any other (sane) compression algorithms. Encoding information this way is really cool, but offers no advantages.

[dorgo]

It won't work. There are 37,607,912,018 prime numbers smaller than 1,000,000,000,000. It's 11 decimal digits vs. 13. All the compression comes from the information that it is a prime number.

To point to the "Nth prime" would require almost as many digits as the prime itself. Mabe it's more efficient for very large primes, but I don't think so.