约数详细分析
我们先来认识一下约数：
约数分正约数和负约数两种，我们一般只讨论正约数。也就是说，接下来所提的约数，只考虑正约数。
如果有一个数k，满足k|n，那么k就是n 的约数（因数），n是k的倍数。
求一个数的约数是信息学竞赛里一个基础的不能再基础的问题。
如果只求一个数，最容易想到的就是枚举。当然枚举也有技巧：n=a×b，因为我们只要知道a，就可以求出b，所以只用枚举a，而不需要把b也枚举。保证a<=b，那么a<=√n，所以只用枚举1-√n所有数，就能得出n所有的约数了。
如果要求1-n内所有的数的约数的个数呢？
和上面是一样，把每个数都枚举一遍就行了，能接受n=200000。
有没有什么更快的方法呢？
看看初一希望杯必备的一个知识点：
N=p1q1 ×p2q2 ×p3q3×…×piqi
根据乘法原理，可以得出n的约数一共有
(q1+1)×(q2+1)×(q3+1)×…(qi+1)个
从上面可以得出：分解质因数及其对应的指数也是一个可行的方法。
具体就是先用筛法求出√n内所有的质数，之后去一个个分解，相乘。
这种方法n=1000000已经是极限了（c++）。其实一个个求的话，这是很优的了。
代码：
#include<cstdio>
#include<cmath>
#define fo(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
const int max=1000000,po=sqrt(max*1.0);
bool bz[po+1];
int f[max+1],p[169];
int main()
{
fo(i,2,po)
{
if (!bz[i]) p[++p[0]]=i;
fo(j,1,p[0])
{
if(max/p[j]<i) break;
bz[i*p[j]]=1;
if (i%p[j]==0) break;
}
}//线性筛法
fo(i,1,max)
{
f[i]=1; int k=i;
fo(j,1,p[0])
{
if (p[j]>sqrt(i*1.0)) break;
if (k==1) break;
int a=0;
while (k%p[j]==0)
{
a++;k/=p[j];
}
f[i]*=a+1;
}//分解质因数
if (k>1) f[i]*=2;//统计大于√i的质因数
}
}
想从根本上提速，关键在于统一求解，换个说法就是利用已知的，去求未知的。
我们观察公式，可以想到：先求出质因数只有p1的所有数的约数的个数，再求出质因数只有p1，p2的所有数的约数的个数，以此类推。 可是复杂度似乎太高了一些，因为每次都要把之前求出的数全部枚举log(pi,max)遍。然而，明显很多的数都会超出范围，所以我们给一个快排，超过max时就能提前退出了。每个数只会被求一遍，所以这一部分的复杂度是线性的，可是快排的时间不能接受，所以我们放弃这个思路。
我们也可以直接深搜指数，时间复杂度是线性的，每个数同样只会被求一遍。但是需要注意许多细节的地方，该退的要退，否则，可能会被一些不必要的计算拖死。代码复杂度有些高，且常数大。
目前最快的方法是线性筛法，线性筛法不仅可以筛质数、欧拉函数，连约数的个数、约数和也是可以筛，前提是找到该类数的性质。
在这里为了方便，我就不再去解释基本的线性筛法了。如果有所不懂，请参考百度文库—《线性筛法求素数的原理与实现》。
--------------------------------------------------------------------------------------------------------------------------------------------------------------
http://wenku.baidu.com/link?url=_pA6Fc0NYYUYfziA4piuzPptF7yTlIZWIAqJXGId3WJ
B_T6J6P3Q02wOBu4XI1z906wmRWutMSWVxWQobIhqrodvlgdeiIBT-PJ3R6KGKoW
--------------------------------------------------------------------------------------------------------------------------------------------------------------
为了理解线性筛法，我费了不少劲。线性筛法的基本思想就是每个数仅被它最小（网上的通用说法是最大，在筛约数的个数中，理解为最小会容易许多，最小的因子其实就是最小的质因子）的因子筛去一遍，那么我们能不能在线性筛法上加一点东西，使它把每个数的约数的个数也维护了呢？
答案当然是可以的。我们可以利用筛性筛法的基本思想，去实现我们的目标。
E[i]表示i的最小的质因子的指数。D[i]表示i的约数的个数。P[j]表示在筛去i的倍数时，枚举到的第j个质数。
在用i去筛掉i的倍数时，如果i和当前的p[j]互质,
那么d[i*p[j]]=d[i]*2,E[i*p[j]]=1；
因为p[j]在i*p[j]中对应的指数是1，所以约数的个数要乘以2。
因为p[1..j-1]和i都互质，所以p[j]也是i*p[j]的最小质因子，e[i*p[j]]也就顺理成章等于1。
否则，就说明：p[j]是i的最小质因子，那么我们之前统计的d[i]便有了用武之地。既然p[j]是i的最小质因子，且我们又知道p[j]做为i的质因子所对应的指数E[i],很容易推出d[i*p[j]]=d[i]/(e[i]+1)×(e[i]+2)，e[i*p[j]]=e[i]+1。
为什么呢？因为p[j]在i中所对应的指数是e[i]，所以p[j]对d[i]的贡献值是(e[i]+1),那么现在我们乘一个p[j],那么指数加1，对d[i*p[j]]贡献值就是了(e[i]+2)，先除以之前的贡献值，再乘上新的，就得到了新的答案。
根据基础线性筛法的特性，此时我们又可以直接退出j的循环了。所以时间非常愉快地是线性的。可以跑过30000000。
若有不懂的人，他们应该拍手庆祝，因为接下来有代码：
#include<cstdio>
#define fo(i,x,y) for (int i=x;i<=y;i++)
using namespace std;
const int mn=30000000;
bool bz[mn+1];
int p[mn+1],e[mn+1],d[mn+1];
int main()
{
d[1]=1;
fo(i,2,mn)
{
if (!bz[i])
{
p[++p[0]]=i; //添加到质数表
d[i]=2; //质数的约数的个数一定是2
e[i]=1; //质数的最小的质因子的指数一定是1
}
fo(j,1,p[0])
if (i%p[j]==0)
{
if (mn/p[j]<i) break;//判断是否超出范围
bz[i*p[j]]=1; //标记倍数
d[i*p[j]]=d[i]/(e[i]+1)*(e[i]+2);//求约数的个数 ,不互质情况。
e[i*p[j]]=e[i]+1; //指数加1
break; //线性筛法核心
} else
{
if (mn/p[j]<i) break;
bz[i*p[j]]=1;
d[i*p[j]]=d[i]*2; //求约数的个数，互质情况。
e[i*p[j]]=1; //指数为1
}
}
}