Pagini recente » Cod sursa (job #2601786) | Cod sursa (job #536591) | Cod sursa (job #2794053) | Cod sursa (job #1555113) | Cod sursa (job #122823)
Cod sursa(job #122823)
#include <stdio.h>
#define DIM 1000001
int v[DIM];
long int p[DIM];
long long tot[DIM];
long long sum;
long int cnt,e,d,k,n,j,i,a;
long int pas;
int main(){
FILE *f = fopen("fractii.in","r");
fscanf(f,"%ld",&n);
fclose(f);
for (i=2;i<=n;i++) {
for (j=2*i;j<=n;j+=i)
v[j]=1;
}
k=0;
for (i=2;i<=n;i++)
if (v[i]==0)
p[++k]=i;
//t(p^e) = (p - 1) * p^(e - 1), p numar prim (din definitie)
//si
//daca p numar prim, p NU divide a,
//t(p^e * a) = t(p^e) * t(a) = (p - 1) * p^(e - 1) * t(a)
tot[1]=1;
tot[2]=1;
for (j=1;(j<=k)&&(p[j]<=n);j++) {
d=p[j];
if (d==2)
pas=d;
else
pas=d;
for (i=d;i<=n;i+=pas)
if (tot[i]==0){
a=i;
e=0;
while (a%d==0) {
e++;
a=a/d;
}
if (a==1)
tot[i]=((long long)(d-1))*(i/d);
else
tot[i]=tot[a]*tot[i/a];
sum+=(tot[i]+tot[i]);
}
}
if (n==1)
sum=1;
else if (n==2) sum=3;
else sum+=3;
FILE *g = fopen("fractii.out","w");
fprintf(g,"%lld",sum);
fclose(g);
return 0;
}