线性筛素数、欧拉函数、莫比乌斯函数、约数个数、约数和

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int p[N];//质数表
int phi[N];//欧拉函数 
int mu[N];//莫比乌斯函数
int d[N];//约数个数
int mi[N];//最小质因子次数
int sigma[N];//约数和
int mp[N];//由最小质因子组成的数的约数和 
bool b[N];//是否为质数 
 
int main(){
//  freopen("num.txt","w",stdout);
    b[0]=b[1]=phi[1]=mu[1]=d[1]=mi[1]=sigma[1]=mp[1]=1;
    for(int i=2;i<=N-5;i++){
        if(!b[i]){
            p[++p[0]]=i;phi[i]=i-1;mu[i]=-1;d[i]=2;
            mi[i]=1;sigma[i]=1+i;mp[i]=1+i;
        }
        for(int j=1;j<=p[0]&&i*p[j]<=N-5;j++){
            b[i*p[j]]=1;
            if(i%p[j]==0){
                phi[i*p[j]]=phi[i]*p[j];
                mu[i*p[j]]=0;
                d[i*p[j]]=d[i]/(mi[i]+1)*(mi[i]+2);
                mi[i*p[j]]=mi[i]+1;
                sigma[i*p[j]]=sigma[i]/mp[i]*(mp[i]*p[j]+1);
                mp[i*p[j]]=mp[i]*p[j]+1;
                break;
            }
            else{
                phi[i*p[j]]=phi[i]*phi[p[j]];
                mu[i*p[j]]=-mu[i];
                d[i*p[j]]=d[i]*d[p[j]];
                mi[i*p[j]]=1;
                sigma[i*p[j]]=sigma[i]*sigma[p[j]];
                mp[i*p[j]]=p[j]+1;
            }
        }
    }
    /*
    int n;
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        printf("数：%d 是否为质数：%d phi值：%d mu值：%d 约数个数：%d 约数和：%d\n",i,b[i]?0:1,phi[i],mu[i],d[i],sigma[i]);
    }
    */
    return 0;
}

参考链接