题意:求n的所有因子和;
思路:类似于筛选法求素数的思想,只有第一次的时候了解过它的思想,然后就只是用来求素数,思想的运用反而少;
筛选法求素数:
int prime()
{
memset(vis, true, sizeof(vis));
for(int i = ; i <= sqrt(N +0.5); i++)
if(vis[i])
for(int j = i << ; j <= N; j += i)
vis[j] = false;///该数倍数的都被筛去了
int k=;
for(int i = ; i <= N; i++)
if(vis[i])
pri[k++]=i;
}
该题也类似,枚举所有的数字 i ,然后枚举可能的倍数 j ,好比 i 就是 i * j 的因子,a[i*j] += i;
打表:
memset(a,,sizeof(a));
for(i=;i<=maxe;i++)
{
for(j=;i*j<=maxe;j++)//类似于筛法求素数
{
a[i*j]=a[i*j]+i;
}
}