1751:分解因数

总时间限制:1000ms 内存限制:65536kB

描述

给出一个正整数a，要求分解成若干个正整数的乘积，即a = a1 * a2 * a3 * ... * an，并且1 < a1 <= a2 <= a3 <= ... <= an，问这样的分解的种数有多少。注意到a = a也是一种分解。

输入

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a (1 < a < 32768)

输出

n行，每行输出对应一个输入。输出应是一个正整数，指明满足要求的分解的种数

样例输入

2
2
20

样例输出

1
4

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int sum=0;
 5 void recur(int N,int i)
 6 {
 7     if(N==1) sum++;
 8     while(i<=N)
 9     {
10         if(N%i==0) recur(N/i,i);
11         i++;
12     }
13     return ;
14 }
15 int main()
16 {
17     int T=0;
18     cin>>T;
19     while(T--)
20     {
21         int N=0;
22         cin>>N;
23         int i=2,res=1;
24         while(i<=N/2)
25         {
26             if(N%i==0)
27             {
28                 sum=0;
29                 recur(N/i,i);
30                 res+=sum;
31             }
32             i++;
33         }
34         cout<<res<<endl;
35     }
36     return 0;
37 }