Pagini recente » Cod sursa (job #2026950) | Istoria paginii runda/ichb_9/clasament | Cod sursa (job #2097935) | Cod sursa (job #332105) | Cod sursa (job #178686)
Cod sursa(job #178686)
#include <stdio.h>
char v[2000002];
long long n,i,j,d[1000000],pr[1000000],f,k[1000000],c,nrp,x,r,sum;
long power(long b,long p){//fctie de ridicare la putere
long rez=1;
while (p){
if ((long)(p&1)==1)
rez*=b;
b*=b;p>>=1;
}
return rez;
}
int main()
{
freopen("fractii.in","r",stdin);
freopen("fractii.out","w",stdout);
scanf("%lld",&n);
//-------------ciur
c++;pr[c]=2;
for(i=3;i*i<=n;i=i+2)
if(!v[i]) {pr[++c]=i;
for(j=3*i;j*j<=n;j=j+2*i) v[j]=1;
}
nrp=c;
//-------------ciur
for (i=2;i<=n;i++)
{
x=i;
j=1;r=0;
while (pr[j]*pr[j]<=i){
if (i%pr[j]==0){
r++;
d[r]=pr[j];
k[r]=0;
while (x%pr[j]==0){
x/=pr[j];
k[r]++;
}
}
j++;
}
if (x!=1){r++;d[r]=x;k[r]=1;}
f=1;
for (j=1;j<=r;j++)
f*=(d[j]-1)*power(d[j],k[j]-1);
sum=(long long)sum+2*f;
}
printf("%lld\n",sum+1);
return 0;
}