Pagini recente » Cod sursa (job #3164934) | Cod sursa (job #149313) | Cod sursa (job #2773177) | Cod sursa (job #2645118) | Cod sursa (job #218055)
Cod sursa(job #218055)
#include<fstream.h>
#include<math.h>
long a[1000001],n,i,ii,j,x,y,p,b[1000001],m,ok;
long long nr,rad;
int main()
{
ifstream f("fractii.in");
ofstream g("fractii.out");
b[0]=2;
b[1]=3;
m=2;
for(i=5;i<=1000;i=i+2)
{ok=1;
for(j=1;b[j]<=sqrt(i);j++)
if(i%b[j]==0){ok=0;break;}
if(ok)b[m++]=i;
}
f>>n;
a[1]=1;
for(i=2;i<=n;i++)
{x=i;
ii=0;;
rad=sqrt(x);
while(b[ii]<=rad && x%b[ii])ii++;
if(b[ii]>rad)a[i]=i-1;
else
{ p=b[ii];
y=1;
while(x%p==0){y=y*p;
x=x/p;
}
y=y/p;
a[i]=(p-1)*y*a[x];
}
}
nr=1;
for(i=2;i<=n;i++)
nr=nr+2*a[i];
g<<nr;
g.close();
return 0;
}