线性筛——约数的个数

如果不会线性筛素数的话，建议先看这篇博客了解一下线性筛素数。
线性寻找约数的个数（积性函数都可以线性筛）主要是在线性筛素数的基础上得到的

用 $f\left(n\right)$f(n) 表示 $n$n 的约数的个数
用 $g\left(n\right)$g(n) 表示 $n$n 的最小质因子的个数

我们知道：
若 $n={\prod }_{i=1}^n{p}_i^{t_i}$n=∏i=1n​piti​​

则 $f\left(n\right)={\sum }_{i=1}^n(t_i+1)$f(n)=∑i=1n​(ti​+1)

所以：
1、当 $n$n 是质数时， $g\left(n\right)=1,f\left(n\right)=2$g(n)=1,f(n)=2
对于 2和3 设 $d=\frac{n}{p}$d=pn​ 其中 $p$p 为 $n$n 的最小质因子
2、当 $p$p 是 $d$d 的某个质因子时， 则 $g\left(n\right)=g\left(d\right)+1,f\left(n\right)=\frac{f\left(d\right)\ast \left(g\right(n)+1)}{g\left(d\right)+1}$g(n)=g(d)+1,f(n)=g(d)+1f(d)∗(g(n)+1)​
3、当 $p$p 与 $d$d 互质时， $g\left(n\right)=1,f\left(n\right)=f\left(d\right)\ast \left(g\right(n)+1)$g(n)=1,f(n)=f(d)∗(g(n)+1)

good luck and have fun!!!
附上代码：

int num[MAXN],d[MAXN];//num存约数个数，d存一个数最小质因子的个数
void fun(int n)
{
	memset(vis,0,sizeof(vis));
	num[1]=1;
	d[1]=1;
	prime[0]=0;
	for(int i=2;i<=n;i++)
	{
		if(!vis[i])
		{
			prime[++prime[0]]=i;
			d[i]=1;
			num[i]=2;
		}
		for(int j=1;j<=prime[0]&&i<=n/prime[j];j++)
		{
			vis[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				d[i*prime[j]]=d[i]+1;
				num[i*prime[j]]=num[i]/(d[i]+1)*(d[i]+2);
				break;
			}
			d[i*prime[j]]=1;
			num[i*prime[j]]=num[i]*2;
		}
	}
}