1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<string> 5 #include<cmath> 6 #include<algorithm> 7 using namespace std; 8 #define MAX 500000 9 bool vis[MAX+5];10 int prime[MAX+5];11 void print_prime(){//线性求素数法12     memset(vis,false,sizeof(vis));13     int i,index=0;//注意初始化！！14     int half=sqrt(MAX*1.0)+1;15     for(i=2;i<half;i++){16         if(!vis[i]){17             prime[index++]=i;18         }19         for(int j=0;j<index&&prime[j]*i<=MAX;j++){20             vis[prime[j]*i]=true;21             if(i%prime[j]==0){22                 break;23             }24         }25     }26 }27 int work(int n){//素数分解28     int i=0,total=1,temp=n;29     for(;prime[i]*prime[i]<=n;i++){30         int sum=1,num=1;31         while(n%prime[i]==0){32             num*=prime[i];33             n/=prime[i];34             sum+=num;35         }36         total*=sum;37     }38     if(n!=1){//可能剩下的落单的最大素数39         total*=n+1;40     }41     return total-temp;42 }43 int main()44 {45     int t;46     cin>>t;47     print_prime();48     //cout<<prime[0]<<endl;49     while(t--){50         int n;51         cin>>n;52         cout<<work(n)<<endl;53     }54     return 0;55 }