11
$\begingroup$

On a computer I can have integers on arbitrary size thanks to GMP, so it's represented in base 2 in memory.

I'm wondering if it's possible in theory to use less memory if I store only prime factors and their exponent, I think it's worthless for most numbers, but I wonder if it works for a very small minority of numbers with large prime factors.

How can I prove me wrong ?

  • 2
    I think for some numbers this would definitely use less memory to store them that way. But finding this factorization is costly, and you would need to revert to the usual representation to perform a sum.2012-10-12
  • 0
    @Joel, for some certainly, but not at all on average.2012-11-17

3 Answers 3