最近本人脑洞大开，发现了一种线性筛约数个数和约数和的一种神奇方法。
网上的方法我看基本都是利用num[i]数组记录i最小的质因子的个数，然后再搞搞。
我认为可以省去num[i]数组，直接进行递推。
我们知道，n的标准分解式为：
那么n的约数个数及约数和分别为：
对于线性筛函数f(i)，只需要知道4个东西。
1：f(1) = ?
很显然，d(1) = 1,o(1) = 1;
2：f(p) = ?，其中p为质数。
同样很显然，d(p) = 2,o(p) = p+1;
3、4：f(i*pj) = ?，i与pj互质或不互质。
若i与pj互质，则我们可以利用积性函数的性质直接推出：
最后思考当i与pj不互质的时候，考虑i，i*pj，i/pj的关系(i与pj不互质即i%pj==0)
设：
则有：
进行换元方便计算，设：
就是把pj那一项去掉
则有：
将第一个式子与第二个相减，得到：
那么就已经出来了，
同理，约数和也可以像这样推出来。
补上代码：
int pr[N],vis[N],d[N],sigma[N],cnt; void make(int n) { d[1] = sigma[1] = 1; for(int i = 2;i<=n;i++) { if(!vis[i])pr[++cnt] = i,d[i] = 2,sigma[i] = i+1; for(int j = 1;i*pr[j]<=n&&j<=cnt;j++) { vis[i*pr[j]] = 1; if(i%pr[j]==0) { d[i*pr[j]] = d[i]*2-d[i/pr[j]]; sigma[i*pr[j]] = pr[j]*(sigma[i]-sigma[i/pr[j]])+sigma[i]; break; }d[i*pr[j]] = d[i]*2; sigma[i*pr[j]] = sigma[i]*(pr[j]+1); } } for(int i = 1;i<=n;i++)printf("%d %d\n",d[i],sigma[i]); }
原文：https://www.cnblogs.com/ldysy2012/p/10390857.html