Cod sursa(job #1699418)
| Utilizator | Data | 7 mai 2016 11:54:36 | |
|---|---|---|---|
| Problema | Fractii | Scor | 40 |
| Compilator | c | Status | done |
| Runda | Arhiva de probleme | Marime | 0.64 kb |
#include <stdio.h>
#include <stdlib.h>
char ciur[1000001];
int euler[1000001];
int main()
{
int n, i, j;
FILE*fi,*fo;
fi=fopen("fractii.in","r");
fo=fopen("fractii.out","w");
fscanf(fi,"%d", &n);
for(i=1;i<=n;i++)
euler[i]=i;
ciur[0]=ciur[1]=1;
for(i=2;i<=n;i++)
if(ciur[i]==0){
euler[i]=i-1;
for(j=2*i;j<=n;j+=i){
euler[j]=euler[j]*(i-1)/i;
ciur[j]=1;
}
}
long long sum=0;
for(i=1;i<=n;i++)
sum+=euler[i];
fprintf(fo,"%lld", 2*sum-1);
fclose(fi);
fclose(fo);
return 0;
}
