分解因数

其实,这是一道非常简单的题,但是我把它想复杂了。。。

分解因数

总时间限制: 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的时候便结束递归,计数器加一。那么,我们便可以从2开始枚举(从1开始会形成死循环:永远无法分解到1),不断用分解得到的数去除(2~这个数)(由于本身也可以作为分解)若能整除便继续对下一位进行操作(有点类似gcd,但是那个是%,其实这才是真正意义上的辗转相“除”)qwq,最终我们便可以得到分解的总数。
好的,您应该理解了
最后,附上本题代码
 1 #include<iostream>
 2 using namespace std;
 3 int j,k,n;
 4 void ac(int s,int m)
 5 {
 6     if(s==1)
 7     {
 8         k++;
 9         return;
10     }
11     else
12     {
13         for(int i=m;i<=s;++i)
14         {
15             if(s%i==0)
16             {
17                 ac(s/i,i);
18             }
19         }
20     }
21 }
22 int main()
23 {
24     scanf("%d",&n);
25     for(j=1;j<=n;++j)
26     {
27         k=0;
28         int t;
29         scanf("%d",&t);
30         ac(t,2);
31         printf("%d
",k);
32     }
33 }
原文地址:https://www.cnblogs.com/yufenglin/p/10029787.html