[数论]线性筛——约数个数与约数和

参考博客
参考博客
参考博客
预备知识点：
大于1的数n可以分解质因数：
n=p1^a1×p2^a2×p3^a3*…*pk^a
n的约数的个数是(a1+1) * (a2+1) * (a3+1)…(ak+1)
我们先用线性筛来筛出素数

bool mark[maxn];
int prim[maxn];
int cnt;
void initial()
{
   
    cnt=0;
    for (int i=2 ; i<N ; ++i)
    {
   
        if (!mark[i])
            prim[cnt++]=i;//存放素数
        for (int j=0 ; j<cnt && i*prim[j]<N ; ++j)
        {
   
            mark[i*prim[j]]=1;//标记为素数
            if (!(i%prim[j]))
                break;
        }
    }
}

求约数个数

n的约数的个数是(a1+1) * (a2+1) * (a3+1)…(ak+1)
我们可以用线性筛筛出当前n的约数个数
证明：
d[i]表示i的约数的个数
num[i]表示i的最小素因子的个数
prim[i]表示第i个素数
分下列情况：

1. i为质数
   因为i为质数，所以素因子只有本身，且指数为1
   所以num[i]=1,d[i]=2(1和本身)
2. i%prim[j]!=0
   说明i不包含prim[j]这个素因子，但是i*prim[j]包含一个素因子prim[j]，所以
   d(i∗prime[j])=(1+r1)∗……∗(1+rk)∗(1+1)=d[i] * d[prim[j]] = d[i] * 2
   而且因为我们是从小到大枚举，所以当前的prim[j]必然是i * prim[j]的最小素因子，所以num[i * prim[j]] = 1
3. i%prim[j]= =0
   i中包含prim[j]，且为i的最小素因子
   d(i∗prime[j])=(1+r1+1)∗……∗(1+rk)
   d(i∗prime[j])=d(i)/(num(i)+1)∗(num(i)+2)
   num(i∗prime[j])=num(i)+1

#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\n",i,d[i]);
	return 0;
}

线性筛约数和

我们用sd(i)表示i的约数和
根据算数基本定理：
sd(n)=(1+p1+p²1+……+p^r11)∗(1+p2+p²2+……+p^r22)∗……∗(1+pk+p²k+……+p^rkk)
最小质因子的那一项是(1+p1+p²1+……+p^r11)
我们用num[i]来表示最小质因子的那一项
证明：
和上面一样分类讨论：

1. i为素数
   sd(i)=i+1num(i)=i+1
2. i%prim[j] ! = 0
   i∗prime[j]里原先没有prime[j]这一项，加上后：
   sd(i∗prime[j])=sd(i)∗sd(prime[j])
   num(i∗prime[j])=1+prime[j]
   （大体思路如上）
3. i%prim[j] = =0
   d(i∗prime[j])=(d(i)/num(i)∗(num(i)∗prime[j])+1
   num(i∗prime[j])=num(i)∗prime[j]+1

代码：

#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\n",i,sd[i]);
	return 0;
}