计算一个整数因子个数

2015-07-12

今天说好的帮小马同学做微软夏令营的机试题目，还好，时间来的及，只是。。。题目略难。暂时搞不定啊！！！

小马同学分给我的题目是求解一个整数的因子个数的问题，这个我以前在《编程之美》上见过，整理下思路，参考一下别人的解释，写出自己的源码。

记不清在《编程之美》多少页了，但是相关题目大概还是记得，就是求解一个整数的阶乘结果又多少个0，实际就是求解质因数2和5的个数，不过这里扩展了一下。

以下是我写的测试程序；在机器上测试了一下，要比直接循环判断的方法快的多。

#include <iostream>
#include <map>

using namespace std;

int w[6600] = {2,3,5,7,11,13,17,19,23,29};   // 初始化素数表
int n = 10;                                  // 素数表边界

bool isPrime(int n)                          // 判断是否为素数
{
    for(int i =0;w[i] * w[i] < n ;++i)
        if(n%w[i] == 0)
            return false;
    return true;
}

int getDivisorNum(int m)
{
    map<int, int> ma;               // kay存放素因子，value存放分解个数

    for(int i=0; m!=1 && i<n; )     // 分解因子,n为素数表边界
        if(m%w[i])
            i++;                    // w[i]不是a的因子,则尝试素数表中下一个素数
        else
            ma[w[i]]++, m/=w[i];    // 是因子，则a的该素数个数加1,a除去该素数

    if(m>(1<<16))                   // int 就没必要
        ma[m]++;                    // 大于2^16的素因子最多只有一个
    int sum = 1;
    map<int,int>::iterator it;
    for(it = ma.begin();it!=ma.end();++it)
       sum *= (1+(*it).second) ;
    return sum;
}

int main()
{
    int a = 4;
    for(int i=31;i<(i<<16);i+=2)    // 计算素数表
        if(isPrime(i))
            w[n++] = i;
    for(int i = 1;i<10000;++i)
        cout<<getDivisorNum(i)<<endl;

    return 0;
}

当然，微软不可能出这么简单的题目，重点在后面，测试用例有一部分是大约10的16次方的，也就说用int类型是不能表示的。上面的程序是不行了，需要考虑大数问题。
这个暂时不考虑了，
其实求解这个问题的关键是一个数学定理：

一个整数的所有因子数等于其每个素因子的个数加一之后的乘积(1+p1)(1+p2)…(1+pn)，其中p1、p2、…、pn分别为该整数的所有n个素因子P1、P2、…Pn的相应个数。

参考