3 ms·
The prime factors of a number takes (about) the same amount of space to list as the number itself.
by Simon_says 7y ago
The prime factors of a number takes (about) the same amount of space to list as the number itself.
- saagarjha 7y agoNotably, even listing the ordinal index of the prime (e.g. that a number is the product of the first, fifth, and tenth primes) takes about the same amount of space as well due to the prime number theorem.
- yholio 7y ago> the average gap between consecutive prime numbers among the first N integers is roughly log(N) So if you are compressing exceptionally large numbers, say, a whole video file, which is likely to contain very long factors, you could shave log2(log(N)) bits for each factor of length N. Seems like the most impractical compression algorithm imaginable.
- Normal_gaussian 7y agoI would assume the intent is to use the fact that most numbers use the same prime factors as the encoding advantage. As in, you're transforming a list of dissimilar numbers into a list of similar ones.