G10 筛法求约数个数

#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的幂次数 
//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;g[i]=1;f[i]=2;}
        
        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]+1;
				f[x]=f[i]/(g[i]+1)*(g[x]+1);
				break;
			}
			g[x]=1;
			f[x]=f[i]*2;
        }
    }
}
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;
}