Pagini recente » Cod sursa (job #922451) | Cod sursa (job #583986) | Cod sursa (job #2650416) | Cod sursa (job #1037635) | Cod sursa (job #477211)
Cod sursa(job #477211)
#include <fstream>
using namespace std;
bool prim[1000000];
int s[100001],x,ind,nr,suma,k;
int lgput(int a,int p)
{
int i,sol=1;
for (i = 0; (1<<i) <= p; ++ i)
{
if ( ((1<<i) & p) > 0)
sol*=a;
a*= a;
}
return sol;
}
int main()
{
int i,j,n;
ifstream fi("fractii.in");
ofstream fo("fractii.out");
fi>>n;
for(i=2;i<=1000000;i++)
if(!prim[i])
{
for(j=i+i;j<=1000000;j+=i)
prim[j]=1;
s[++k]=i;
}
suma=0;
for(i=2;i<=n;i++)
{
x=i;
ind=1;
for(j=1;j<=k and s[j]<=x;j++)
if(!(x%s[j]))
{
nr=0;
while(!(x%s[j])) { nr++; x/=s[j]; }
ind*=(s[j]-1)*lgput(s[j],nr-1);
}
suma+=ind;
}
fo<<suma*2+1<<"\n";
return 0;
}