How many combinations are there to factorize a given integer into two numbers.

Question

Hey guys I'm trying to solve a number theory Problem on codeforces. Part of the solution is to figure out how many ways are there to factorize a given number $N$ into $N=AB$. I can illustrate with an example what I mean. Let's look at the number 30. We have that $30=2*3*5$. Thus we find that $30=6*5$, $30=10*3$, $30=15*2$, $30=30*1$. So we have four different ways Since $*$ is commutative we can switch these two numbers and we find 8. If in the Prime Factorization are no prime numbers appearing twice the anwser for the Problem is ways to factorize N=$2^{number\ of \ prime factors \ of \ N}$. But what is the anwser if there are more than one prime factors appearing like $20=2*2*5$?

thank you for the anwsers!

Answer 1

This is equivalent to dividing the number of divisors by $2$, since if $N =AB$, $A$ determines $B$. However, you have to be careful about squares.

If $n = \prod p_i ^{\alpha_i}$ not a square for the $p_i$ distinct primes then the answer is $$\frac{\tau(n)}{2} = \frac{\prod (\alpha_i + i) }{2}$$

If $n$ is a square, then you have the case where the pair $(\sqrt{n}, \sqrt{n})$ is not counted twice so the answer is

$$\frac{\tau (n)+1}{2}$$

Hence, the answer in general is

$$\lceil \frac{\tau(n)}{2} \rceil$$

Answer 2

The number of divisors of a number $$n=\prod_i p_i^{a_i}$$ where $p_i$ are the prime numbers and $a_i$ are their multiplicities is determined by the expression:$$\sigma_0(n)=\prod_{i}(a_i+1).$$

Particularly if the number $n$ is square-free ($\forall p_i:\ a_i=0,1$) one obtains the formula $\sigma_0(n)=2^k$ where $k$ is the number of prime factors of $n$ as you have already found.