西格瑪函數σ 線性篩求約數和

​​http://www.elijahqi.win/archives/1247​​​

解法：待填坑

其實這個完全可以拓展到線性篩求積性函數

因為非完全積 是以在兩數不互質的情況下不可以直接相乘

#include<cstdio>
#define N 110000000
int sigma[N],min_factory_a[N],prime[N/10],not_prime[N],n; 
int main(){
    freopen("ex1.in","r",stdin);
    freopen("ex1.out","w",stdout);
    scanf("%d",&n);sigma[1]=1;int top=0;
    for (int i=2;i<=n;++i){
        if (!not_prime[i]){
            sigma[i]=i+1;prime[++top]=i;min_factory_a[i]=i;
        }
        for (int j=1;prime[j]*i<=n;++j){
            not_prime[prime[j]*i]=1;
            if (i%prime[j]==0){
                if (i*prime[j]==min_factory_a[i]*prime[j]) sigma[i*prime[j]]=sigma[i]+prime[j]*i;else
                sigma[i*prime[j]]=sigma[i]/sigma[min_factory_a[i]]*sigma[min_factory_a[i]*prime[j]];
                min_factory_a[i*prime[j]]=min_factory_a[i]*prime[j];
                break;
            }sigma[i*prime[j]]=sigma[i]*(prime[j]+1);
            min_factory_a[i*prime[j]]=prime[j];
        }
    }
    for (int i=1;i<=n;++i) printf("%d\n",sigma[i]);
    return 0;
}