0
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ @user That is already detailed in the question in more than one place: the comment about $*$ being commutative, the working formula for squarefree $N$, and the lack of any mention that $A\le B$. $\endgroup$
    – Erick Wong
    Mar 21 '21 at 21:43
1
$\begingroup$

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$$

$\endgroup$
2
  • 2
    $\begingroup$ The notation $\sigma(n)$ is a unconventional here, usually it would mean the sum of all divisors rather than the count of divisors. While you could use $\sigma_0(n)$ (sum of the 0th powers of divisors), it is probably more common to use $d(n)$ or $\tau(n)$. $\endgroup$
    – Erick Wong
    Mar 21 '21 at 21:46
  • $\begingroup$ my bad, sometimes confuse the two notations $\endgroup$ Mar 21 '21 at 21:51
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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