哪位大牛帮小弟解决一个程序问题？

题目：
此题是正整数分解的问题。要求给出任意正整数n,可以输出小于n的正整数的乘积的个数。
例如： 例如：12 = 1 * 12                                                 30 = 1 * 30

                = 3 * 4                                                        = 2 * 3 * 5 

                = 2 * 6                                                        = 6 * 5

                = 2 * 2 * 3                                                   = 2 * 15

             总合计有4种因子分解的方法。                                      = 3 * 10

                                                                        总合计有5种因子分解的方法。

    本题目的要求即为输入正整数n ，输出因子分解方式的个数。即    T(12) = 4,    T(30) = 5

10 个解决方案

#1

题目：
此题是正整数分解的问题。要求给出任意正整数n,可以输出小于n的正整数的乘积的个数。
例如： 例如： 30 = 1 * 30
               =  2 * 3 * 5  
               = 6 * 5
               = 2 * 15
               = 3 * 10

   总合计有5种因子分解的方法。

   本题目的要求即为输入正整数n ，输出因子分解方式的个数。即 T(12) = 4, T(30) = 5

#2

解题 已经不是编程问题了吧
应该是逻辑思维问题了吧

#3

找出质因数，然后求组合数
如30=2*3*5，则30=1*（2*3*5）=2*（3*5）=3*（2*5）=5*（2*3）=2*3*5

#4

引用 3 楼 ouyh12345 的回复:

找出质因数，然后求组合数
如30=2*3*5，则30=1*（2*3*5）=2*（3*5）=3*（2*5）=5*（2*3）=2*3*5

整数的质因数分解可以得到，就是组合数的时候确实比较麻烦，感觉像是一个NPC问题呀！万一要是有相同的质因数就麻烦了，比如24=2*2*2*3

#5

引用 2 楼 hongwenjun 的回复:

解题 已经不是编程问题了吧
应该是逻辑思维问题了吧

这个是我的错误，本来以为写俩例子，但是在编辑框里编完，一发贴就前提了好几行，莫怪莫怪！

#6

走素因子分解还是简单问题复杂化了.

对于一个n，我们用1...sqrt(n)去试除n，这样就获得了所有的 因子。

将这些因子从小到大排列，然后做递归。

比如因子是：2 6 8 12 ，n=1152

如果你选择了2，那么今后的因子只能从2 7 9 19选（当然前提是n能整出它们），n=1152/2；
下一次递归你可以选择6，那么今后的因子只能从6 8 12选（当然前提是n能整出它们），n=1152/2/6.

就这样。

#7

引用 6 楼 qq120848369 的回复:

走素因子分解还是简单问题复杂化了.

对于一个n，我们用1...sqrt(n)去试除n，这样就获得了所有的因子。

将这些因子从小到大排列，然后做递归。

比如因子是：2 6 8 12 ，n=1152

如果你选择了2，那么今后的因子只能从2 7 9 19选（当然前提是n能整出它们），n=1152/2；
下一次递归你可以选择6，那么今后的因子只能从6 8 12选（当然前提是n能……

会不会有所遗漏啊？

#8

（当然前提是n能整出它们）

#9

linux-6v95:/home/owenliang/csdn/cAndCpp # cat main.cpp
#include <iostream>
#include <algorithm>
using namespace std;

#define SIZE 10000

int yin[SIZE];
int selectYin[SIZE];
int nYin;

void printResult(int,int);

void getYinZi(int num)
{
        nYin=0;

        for(int i=2;i<num;++i)
        {
                if(num%i==0)
                {
                        yin[nYin++]=i;
                }
        }

        printResult(0,num);
}

void printResult(int cur,int n)
{
        if(n==1)
        {
                for(int i=0;i<cur;++i)
                {
                        for(int j=0;j<selectYin[i];++j)
                        {
                                cout<<yin[i]<<" ";
                        }
                }

                cout<<endl;

                return;
        }

        if(cur>=nYin)
        {
                return;
        }

        int m=1,cnt=0;

        while(n%m==0)
        {
                selectYin[cur]=cnt;
                printResult(cur+1,n/m);
                m*=yin[cur];
                ++cnt;
        }
}

int main()
{
        int num;

        cin>>num;
        getYinZi(num);

        return 0;
}
linux-6v95:/home/owenliang/csdn/cAndCpp # ./main      
64
8 8 
4 16 
4 4 4 
2 32 
2 4 8 
2 2 16 
2 2 4 4 
2 2 2 8 
2 2 2 2 4 
2 2 2 2 2 2 
linux-6v95:/home/owenliang/csdn/cAndCpp # 

#10

可以这样考虑，当某个数n分解成几个数乘积 x1 * x2 * x3时，肯定有大小之分，我们肯定能找到其中最小的数，比如是x1，则x2，x3肯定比x1大，我们在确定了x1之后，剩下的任务即找出所有n/x1能分解成几组数相乘，并且分解的每组中每个数都要比x1大，所以解法是：
一，2...sqrt(n)找到所有能被n整除的数，如n=12时找到2，3
二，针对找出的2，3，分别处理：
   1）最小数是2时，递归求12/2也就是6的分组数，同时注意每个数不得小于2（本身算合法的一组，即 1*本身）.
   2）最小数是3时，递归求12/3也就是4的分组数，同时注意每个数不得小于3（本身除外），所以只有自己本身这一组。
三，把1）跟2）的相加，再加1（本身）