G11 筛法求约数和

#include <bits/stdc++.h>
using namespace std;
typedef long long LL; 
const int N=5e7;
int p[N+10], pr; bool v[N+10];
int n, g[N+10], f[N+10]; 
//g[i]表示i的最小因子a的等比数列和(1+a+a^2+a^3+…)
//f[i]表示i的约数和 
void init() 
{
    pr=0; memset(v, 0, sizeof(v));
    f[1]=1;
    for(int i=2; i<=n; i++)
    {
        if(v[i]==0){ p[++pr]=i; f[i]=g[i]=i+1; }
		    
        for(int j=1; (j<=pr) && (i*p[j] <=n); j++)
        {
        	int x = i*p[j];
            v[x] = 1;
            if(i%p[j]==0)//此时p[j]是i的最小因子，也是x的最小因子 
			{
				g[x] = g[i] * p[j] + 1;
				f[x] = f[i] / g[i] * g[x];
				break;
			}
			else
			{
				g[x] = p[j] + 1;
				f[x] = f[i] * g[x];
			}
        }
    }
}
int main()
{
	scanf("%d", &n);
	init();
	LL ans=0; for(int i=1; i<=n; i++) ans += f[i];
	printf("%lld\n", ans);
	return 0;
}

G11 筛法求约数和

#include<bits/stdc++.h>
using namespace std;
typedef long long LL; 
const int N=5e7;
int p[N+10],pr;bool v[N+10];
int n,g[N+10],f[N+10]; 
//g[i]表示i的最小因子a的等比数列和(1+a+a^2+a^3+…)
//f[i]表示i的约数和 
void init() 
{
    pr=0;memset(v,0,sizeof(v));
    f[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(v[i]==0){p[++pr]=i;f[i]=g[i]=i+1;}
		    
        for(int j=1;(j<=pr)&&(i*p[j]<=n);j++)
        {
        	int x=i*p[j];
            v[x]=1;
            if(i%p[j]==0)//此时p[j]是i的最小因子，也是x的最小因子 
			{
				g[x]=g[i]*p[j]+1;
				f[x]=f[i]/g[i]*g[x];
				break;
			}
			else
			{
				g[x]=p[j]+1;
				f[x]=f[i]*g[x];
			}
        }
    }
}
int main()
{
	scanf("%d",&n);
	init();
	LL ans=0;for(int i=1;i<=n;i++)ans+=f[i];
	printf("%lld\n",ans);
	return 0;
}