Pagini recente » Cod sursa (job #1343474) | Cod sursa (job #1113523) | Cod sursa (job #3277501) | Cod sursa (job #502411) | Cod sursa (job #655237)
Cod sursa(job #655237)
#include<stdio.h>
using namespace std;
long long nr,n,s,p,i,j,aux,nr1,a[1000002],pr[1000002];
long pow(long long x,long long y)
{
int i1;
long long p1=1;
for(i1=1;i1<=y;i1++)
p1=1LL*p1*x;
return p1;
}
int main()
{
freopen("fractii.in","r",stdin);
freopen("fractii.out","w",stdout);
scanf("%d",&n);
a[1]=1;
for(i=1;i<=n;i++)
if(a[i]==0)
{
nr++;
pr[nr]=i;
for(j=i*i;j<=n;j=j+i)
a[j]=1;
}
s=0;
for(i=2;i<=n;i++)
{
p=1;
if(i==100)
p=1;
aux=i;
for(j=1;j<=nr&&pr[j]*pr[j]<=aux;j++)
if(aux%pr[j]==0)
{
nr1=0;
while(aux%pr[j]==0)
{
nr1++;
aux=aux/pr[j];
}
p=1LL*p*pow(pr[j],nr1-1)*(pr[j]-1);
}
if(aux!=1)
{
j=n+1;
pr[j]=aux;
nr1=1;
p=1LL*p*pow(pr[j],nr1-1)*(pr[j]-1);
}
s=s+p;
}
printf("%lld\n",1LL*s*2+1);
return 0;
}