Factoring: number of ways to factorize a number.

It happens that you learn a new thing or two everyday. Today, I learned how to find the number of ways to factorize a number where order of divisors is not important (4 X 2 is same as 2 X 4).

Let's think about a the problem :

Suppose your number is n. Also, n can be factorized as n = a x b. So, the number of ways to factorize n will be equal to 1 + no. of ways to factorize b !

So, we need a recursive approach. Here's a code in C++ for doing such that:

//This code finds the no. of ways to factorise a number.
//It is based on a recursve code.
//Order is not important i.e; 2 X 4 is same as 4 X 2.
#include <cstdio>
#include <iostream>
using namespace std;

int countWays(int n,int factor)
{
   int i;
   int count=0; //This variable will contain the number of ways
  for(i=factor;i*i<=n;i++)
    if(n%i==0)
     count += countWays(n/i,i) + 1;
 return count;    
}  
int main()
{
    int n,t;
 scanf("%d",&t); //Test cases.
 while(t--)
 {
  scanf("%d",&n);
  printf("%d\n",countWays(n,2));
 }
 return 0;
}

Try to understand it ..its very simple !