Cod sursa(job #639892)
Utilizator | Simion Stefan juliuss | Data | 24 noiembrie 2011 11:11:43 |
---|---|---|---|
Problema | Fractii | Scor | 0 |
Compilator | c | Status | done |
Runda | Arhiva de probleme | Marime | 0.49 kb |
#include <stdio.h>
#define LEN 1000001
int n, count;
int
main(void)
{
char* phi = (char *)malloc(LEN * sizeof(char));
int i, j;
freopen("fractii.in", "r", stdin);
freopen("fractii.out", "w", stdout);
scanf("%d", &n);
for (i = 1; i <= n; i++)
phi[i] = i;
for (i = 2; i <= n; i++)
if (phi[i] == i)
for (j = i; j <= n; j += i)
phi[j] /= i, phi[j] *= (i - 1);
for(i = 2; i <= n; i++)
count += 2 * phi[i];
printf("%d ", count + 1);
return 0;
}