Writing $n$ as $a*b$ This was asked in a facebook interview . 

Given a number, find the number of ways you can split it into two
  numbers such that each of them is greater than $1$ and both the
  numbers don't have a common divisor and their product is equal to the
  given number

can somebody give a code with an explanation ??
 A: First, you can decompose $n$ in a product of prime numbers : $n = p_1^{n_1}...p_r^{n_r}$. Then, you only have to choose a subset $I \subset \{1, 2, ..., r \}$, $I \neq \emptyset$, $I \neq \{1, 2, ..., r \}$. You will have $a = \prod_{j \in I} p_j^{n_j}$, and $b = n/a$.
So the number of ways you are looking for is the number of such $I$ subsets, e.g. $2^r - 2$.
Pseudo-code :
if (n < 2) return 0;
r = 0; // Number of prime factors of n
n' = n;
for i = 2 to n do {
    if (n' mod i == 0)
        r++;
    while (n' mod i == 0)
        n' = n'/i;
    if (n' == 1) // All prime factors have been treated.
        break;
}
return 2^r - 2;

A: I'll give the pseudo code:
for (prime p)
   { if (n==0 (mod p))
       k=max{j: n==0 (mod p^j)}
       we can then write out n=p^j(n/p^j)
   }

such that there are $|P(p \in prime: n=0 (mod p))|$ different possibilities.
So if $ n=\prod_{i=1}^{k}p_i^{r_i}  $, then we can write n out like this in $ (2^k-2)/2=2^{k-1}-1 $ different ways, because we are not interested in the empty set or all of the set of indices (because that would be the entire number itself, and also choosing a set's compliment is the same as choosing the set itself (that's why we divide by 2).
