线性筛约数个数和，约数和
一，线性筛约数个数和
根据唯一分解定理，可得：
对于每个n的约束，肯定是由以上质因数(p_k)相乘得来的，那么根据乘法原理，每个质因数都可以选择(0)到(r_k)这(r_k+1)个选择。
那么n的约数个数即为
筛的过程中需要保存n的最小质因子的出现个数即(r_1)。
我们设d(i)表示(i)的约数个数和，num(i)表示i的最小质因数的个数。
那么就可以愉快地分情况讨论了。
(一)，如果当前数是素数，那么可得：
(二)，当前数取模枚举的第j个素数不为0，即(i％prime[j]!=0)。
我们要去更新(i*prime[j])的有关信息。
首先我们知道(i*prime[j])这个数中之前一定不包含(prime[j])这个质因数。
那么约数个数和就要加上(prime[j])的，也就是：
然后对于最小质因子，因为ｊ是从小到大枚举的，所以(i*prime[j])这个数的最小质因子也就是(prime[j])
所以就可以得到：
(三)，当前数取模枚举的第j个素数为0，即(j%prime[j]==0)
依旧要去更新(i*prime[j])的信息。
这个时候(i*prime(j))中已经存在(prime[j])这个质因子了，并且(prime[j])也一定是(i*prime[j])的最小质因子，所以就可以得到：
那么怎么从(d(i))转移呢？
这个时候就可以用到我们之前维护的num(i)了。
转移也就非常简单了：
num也要转移，加上最小质因子(prime[j])的贡献也就是：
综上，就可以写出筛质因数个数的代码了。
code:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int wx=1017;
int isprime[wx],prime[wx],d[wx],num[wx];
int tot,n,m;
inline int read(){
int sum=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}
return sum*f;
}
void Euler(){
memset(isprime,1,sizeof isprime); d[1]=1;
for(int i=2;i<=n;i++){
if(isprime[i]){
prime[++tot]=i;
d[i]=2;
num[i]=1;
}
for(int j=1;j<=tot&&i*prime[j]<=n;j++){
isprime[i*prime[j]]=0;
if(i%prime[j]==0){
d[i*prime[j]]=d[i]/(num[i]+1)*(num[i]+2);
num[i*prime[j]]=num[i]+1; break;
}
else{
d[i*prime[j]]=d[i]*d[prime[j]];
num[i*prime[j]]=1;
}
}
}
}
int main(){
n=read(); Euler();
for(int i=1;i<=n;i++)printf("%d %d
",i,d[i]);
return 0;
}
二，线性筛约数和
我们设(sd(i))表示i的约数和。
在算数基本定理中，可以得：
那么根据这个式子就可以开始干了。。。
这个时候我们需要记录最小质因子的那一项也就是((1+p_1+p_1^2+……+p_1^{r_1}))。
可以设(sd(i))表示i的约数和。设(num(i))表示我们需要记录的最小质因子的那一项(等比数列？)。
好了，开始分情况讨论吧。
(一)，当前数是一个素数：
易知：
(二)，当前数取模枚举的质数不等于0
易知(i*prime[j])里原先没有(prime[j])这一项，加上这一项之后可得：
(好吧我又犯懒了。。。但是思路是和上面一样的)
同时更新一下(num(i*prime[j]))。
这是因为质因子从小到大枚举，那么(i*prime[j])的最小质因子就应该是(prime[j])，那么(num(i*prime[j]))也就应该等于(num(prime[j]))
(三)，当前数取模枚举的质数等于0
那么(sd(i*prime[j]))中的第一项也就是(num(i*prime[j]))一定是(prime[j])的一项。
也就是((1+p_i+p_i^2+……+p_i^{r_i}))这个时候要变成((1+p_i+p_i^2+……+p_i^{r_i}+p_i^{r_i+1}))，那么只需要所有的都乘以一个(p_i)也就是(prime[j])，然后再加一个一就好了。
即：
然后(num(i*prime[j]))依旧是(prime[j])这一项，那么就是：
这样，我们又可以开始愉快的写代码啦。。。
code:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int wx=1017;
inline int read(){
int sum=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}
return sum*f;
}
int isprime[wx],sd[wx],num[wx],prime[wx];
int n,tot;
void Euler(){
memset(isprime,1,sizeof isprime); sd[1]=1;
for(int i=2;i<=n;i++){
if(isprime[i]){
prime[++tot]=i;
sd[i]=1+i; num[i]=1+i;
}
for(int j=1;j<=tot&&prime[j]*i<=n;j++){
isprime[i*prime[j]]=0;
if(i%prime[j]!=0){
sd[i*prime[j]]=sd[i]*sd[prime[j]];
num[i*prime[j]]=prime[j]+1;
}
else{
sd[i*prime[j]]=sd[i]/num[i]*(num[i]*prime[j]+1);
num[i*prime[j]]=num[i]*prime[j]+1; break;
}
}
}
}
int main(){
n=read(); Euler();
for(int i=1;i<=n;i++)printf("%d %d
",i,sd[i]);
return 0;
}