[Math] Determine the number of factors for extremely large numbers.

algorithmsdivisibilityfactoringnumber theory

An offshoot from a related question, is there a way to determine the number of possible factors (odd, even, prime, etc.) for extremely large integers without actually factoring them?

Even an estimation would help as long as it has some relevance to the number in question.

Best Answer

As others have noted, there are bounds. But you can have, say, two 1000-digit numbers, differing only in their 778th digit, one of the numbers having zillions of factors, the other being prime, or a product of two primes. There is, in general, no way to get much information about the number of possible factors (or odd factors, or even factors, or prime factors, or repeated factors, etc., etc.) without factoring the number.

Related Question