Pagini recente » Rezultatele filtrării | Rezultatele filtrării | rayman | Cod sursa (job #1747794) | Cod sursa (job #66532)
Cod sursa(job #66532)
#include<stdio.h>
#include<math.h>
typedef struct
{
long x, e;
} factor;
factor v[10];
long n, contor, nr, a[1000002];
void descomp(long x)
{
int exp, d;
d=2;
nr=0;
while (x!=1)
{
exp=0;
if (x%d==0)
{
nr++;
while (x%d==0)
{
exp++;
x/=d;
}
v[nr].e=exp;
v[nr].x=d;
}
d++;
}
}
long totient(long x)
{
long i, c=1;
for (i=1; i<=nr; i++)
c*=((v[i].x-1)*pow(v[i].x,v[i].e-1));
return c;
}
void ciur(long x)
{
long i;
for (i=4; i<=x; i+=2)
a[i]=1;
for (i=3; i<=x; i+=2)
{
if (a[i]==0)
{
long j=i*2;
while (j<n)
{
a[j]=1;
j+=i;
}
}
}
}
void citire()
{
freopen("fractii.in","r",stdin);
scanf("%ld",&n);
}
int main()
{
citire();
long i;
contor=1;
ciur(n);
for (i=2; i<=n; i++)
{
if (a[i]==0) contor+=i-1;
else
{
descomp(i);
contor+=totient(i);
}
}
freopen("fractii.out","w",stdout);
printf("%ld",contor*2-1);
return 0;
}