Cod sursa(job #247612)
Utilizator | Alexandru-Iancu Caragicu Bit_Master | Data | 23 ianuarie 2009 12:59:47 |
---|---|---|---|
Problema | Fractii | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.46 kb |
#include <stdio.h>
const int N = 1000001;
int main()
{
long long n, e[N],nrc=1,i,j;
freopen ("fractii.in","r",stdin);
freopen ("fractii.out","w",stdout);
scanf("%lld",&n);
for (i = 1; i <= n; ++i)
e [i] = i;
for (i = 2; i <= n; ++i)
if (e [i] == i)
for (j = i; j <= n; j+=i)
e [j] = e [j] / i * (i - 1); // e [x] Numarul de numere prime intre ele cu x;
for (i = 2; i <= n; ++i)
nrc+= 2 * e [i];
printf ("%lld",nrc);
return 0;
}