0
$\begingroup$

$6983776800$ in binary has 33 bits but has $2034$ positive divisors.

If a list of divisors were to be logarithmic in N, it needs to take less than 33 bits.

I believe there is an infinite amount of numbers with more divisors than the bits used to represent them.

Thus it is not possible for any algorithm to create a list using log-space.

So given the worst case, that $N$ has a vast amount of divisors what is the true space-complexity?

$\endgroup$

1 Answer 1

4
$\begingroup$

“Saving all divisors” is just not a clever way to go about it. It’s much better to factor N into the product of powers of distinct primes, which has about the same size as N, and all divisors can be enumerated from that easily.

But then, if N has n bits, it can be the product of about n/log n primes of log n bits each, so there are about 2^(n / log n) possible products of n/2 bits each on average. So the logarithm of the size of all factors is about n/log n. I’m sure you can do this a bit more precise.

$\endgroup$
1
  • $\begingroup$ If we want to store factorisations for all integers up to some maximum, a compact way is to store just the smallest prime factor $p[i]$ for each $i$. The complete set of prime factors can then be recovered for any $i$: it's $p[i]$, plus the result of recursing on $i/p[i]$. $\endgroup$ Aug 18, 2021 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.