Pagini recente » Cod sursa (job #1503098) | Cod sursa (job #1536277) | Cod sursa (job #1195109) | Cod sursa (job #697496) | Cod sursa (job #130440)
Cod sursa(job #130440)
#include<stdio.h>
#define N 1000004
char c[N];
int b[90000];
long long ve[N];
int main()
{
int i,j,k,x,v,t,w;
freopen("fractii.in","r",stdin);
freopen("fractii.out","w",stdout);
unsigned long long f=0,f1;
c[0]=c[1]=1;
for(i=4; i<N; i+=2)
c[i]=1;
for(i=3; i*i<N; i+=2)
{
if(!c[i])
for(j=i+i+i; j<N; j=j+i+i)
c[j]=1;
}
b[1]=2;
k=1;
for(i=3; i<N; i+=2)
{
if(!c[i])
b[++k]=i;
}
scanf("%d",&x);
ve[1]=1;
if(x>1)
{
for(i=2; i<=x; i++)
{
if(!c[i])
{
f=f+i-1;
f1=i-1;
}
else
{
v=0;
t=1;
w=i;
for(j=1; (j<=k)&&(v==0); j++)
{
if(w%b[j]==0)
{
v=1;
while(w%b[j]==0)
{
w=w/b[j];
t=t*b[j];
}
}
}
if(t==i)
f1=(b[j-1]-1)*(i/b[j-1]);
else
f1=ve[t]*ve[w];
f=f+f1;
}
ve[i]=f1;
}
f=2*f+1;
printf("%llu\n",f);
}
else
printf("1\n");
return 0;
}